链表翻转的变形实战
链表翻转的变形实战
接下来我们来看看链表翻转的变形:
变形题 1：给定一个链表的头结点 head,以及两个整数 from 和 to ,在链表上把第 from 个节点和第 to 个节点这一部分进行翻转。例如：给定如下链表，from = 2, to = 4 head–>5–>4–>3–>2–>1 将其翻转后，链表变成 head–>5—>2–>3–>4–>1
有了之前翻转整个链表的解题思路，现在要翻转部分链表就相对简单多了,主要步骤如下:
1、根据 from 和 to 找到 from-1, from, to, to+1 四个结点(注意临界条件，如果 from 从头结点开始，则 from-1 结点为空, 翻转后需要把 to 设置为头结点的后继结点， from 和 to 结点也可能超过尾结点,这两种情况不符合条件不翻转)。
2、对 from 到 to 的结点进行翻转
3、将 from-1 节点指向 to 结点，将 from 结点指向 to + 1 结点
知道了以上的思路，代码就简单了,按上面的步骤1，2，3 实现，注释也写得很详细，看以下代码（对 from 到 to 结点的翻转我们使用迭代翻转，当然使用递归也是可以的，限于篇幅关系不展开，大家可以尝试一下）。
/**
* 迭代翻转 from 到 to 的结点
*/
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {
Node fromPre = null; // from-1结点
Node from = null; // from 结点
Node to = null; // to 结点
Node toNext = null; // to+1 结点
// 步骤 1：找到 from-1, from, to, to+1 这四个结点
Node tmp = head.next;
int curIndex = 1; // 头结点的index为1
while (tmp != null) {
if (curIndex == fromIndex-1) {
fromPre = tmp;
} else if (curIndex == fromIndex) {
from = tmp;
} else if (curIndex == toIndex) {
to = tmp;
} else if (curIndex == toIndex+1) {
toNext = tmp;
}
tmp = tmp.next;
curIndex++;
}
if (from == null || to == null) {
// from 或 to 都超过尾结点不翻转
throw new Exception("不符合条件");
}
// 步骤2：以下使用循环迭代法翻转从 from 到 to 的结点
Node pre = from;
Node cur = pre.next;
while (cur != toNext) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 步骤3：将 from-1 节点指向 to 结点（如果从 head 的后继结点开始翻转，则需要重新设置 head 的后继结点），将 from 结点指向 to + 1 结点
if (fromPre != null) {
fromPre.next = to;
} else {
head.next = to;
}
from.next = toNext;
}变形题 2：给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 : 给定这个链表：head–>1->2->3->4->5 当 k = 2 时，应当返回: head–>2->1->4->3->5 当 k = 3 时，应当返回: head–>3->2->1->4->5 说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
只要我们能找到翻一组 k 个结点的方法，问题就解决了（之后只要重复对 k 个结点一组的链表进行翻转即可）。
接下来，我们以以下链表为例
来看看怎么翻转 3 个一组的链表（此例中 k = 3）
- 首先，我们要记录 3 个一组这一段链表的前继结点,定义为 startKPre,然后再定义一个 step, 从这一段的头结点 (1）开始遍历 2 次，找出这段链表的起始和终止结点，如下图示
- 找到 startK 和 endK 之后，根据之前的迭代翻转法对 startK 和 endK 的这段链表进行翻转
- 然后将 startKPre 指向 endK,将 startK 指向 endKNext，即完成了对 k 个一组结点的翻转。
知道了一组 k 个怎么翻转，之后只要重复对 k 个结点一组的链表进行翻转即可，对照图示看如下代码应该还是比较容易理解的
/**
* 每 k 个一组翻转链表
* @param k
*/
public void iterationInvertLinkedListEveryK(int k) {
Node tmp = head.next;
int step = 0; // 计数，用来找出首结点和尾结点
Node startK = null; // k个一组链表中的头结点
Node startKPre = head; // k个一组链表头结点的前置结点
Node endK; // k个一组链表中的尾结点
while (tmp != null) {
// tmp 的下一个节点,因为由于翻转，tmp 的后继结点会变,要提前保存
Node tmpNext = tmp.next;
if (step == 0) {
// k 个一组链表区间的头结点
startK = tmp;
step++;
} else if (step == k-1) {
// 此时找到了 k 个一组链表区间的尾结点（endK）,对这段链表用迭代进行翻转
endK = tmp;
Node pre = startK;
Node cur = startK.next;
if (cur == null) {
break;
}
Node endKNext = endK.next;
while (cur != endKNext) {
Node next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 翻转后此时 endK 和 startK 分别是是 k 个一组链表中的首尾结点
startKPre.next = endK;
startK.next = endKNext;
// 当前的 k 个一组翻转完了，开始下一个 k 个一组的翻转
startKPre = startK;
step = 0;
} else {
step++;
}
tmp = tmpNext;
}
}时间复杂度是多少呢，对链表从头到尾循环了 n 次，同时每 k 个结点翻转一次，可以认为总共翻转了 n 次，所以时间复杂度是O(2n),去掉常数项，即为 O(n)。注：这题时间复杂度比较误认为是O(k * n),实际上并不是每一次链表的循环都会翻转链表，只是在循环链表元素每 k 个结点的时候才会翻转
变形题 3:变形 2 针对的是顺序的 k 个一组翻转，那如何逆序 k 个一组进行翻转呢
例如：给定如下链表， head–>1–>2–>3–>4–>5 逆序 k 个一组翻转后，链表变成
head–>1—>3–>2–>5–>4 （k = 2 时）
这道题是字节跳动的面试题，确实够变态的，顺序 k 个一组翻转都已经属于 hard 级别了，逆序 k 个一组翻转更是属于 super hard 级别了，不过其实有了之前知识的铺垫，应该不难，只是稍微变形了一下，只要对链表做如下变形即可
代码的每一步其实都是用了我们之前实现好的函数，所以我们之前做的每一步都是有伏笔的哦！就是为了解决字节跳动这道终极面试题！
/**
* 逆序每 k 个一组翻转链表
* @param k
*/
public void reverseIterationInvertLinkedListEveryK(int k) {
// 先翻转链表
iterationInvertLinkedList();
// k 个一组翻转链表
iterationInvertLinkedListEveryK(k);
// 再次翻转链表
iterationInvertLinkedList();
}由此可见，掌握基本的链表翻转非常重要！难题多是在此基础了做了相应的变形而已
总结
本文详细讲解了链表与数组的本质区别，相信大家对两者的区别应该有了比较深刻的认识，尤其是程序局部性原理，相信大家看了应该会眼前一亮，之后通过对链表的翻转由浅入深地介绍，相信之后的链表翻转对大家应该不是什么难事了，不过建议大家亲自实现一遍文中的代码哦，这样印象会更深刻一些！
有时候看起来思路是这么一回事，但真正操作起来还是会有不少坑，纸上得来终觉浅，绝知此事要躬行！
来源 | 五分钟学算法
作者 | 程序员小吴
