入门到进阶:链表翻转
入门到进阶:链表翻转
接下来我们会重点看一下链表的翻转，链表的翻转可以衍生出很多的变形，是面试中非常热门的考点，基本上考链表必考翻转！所以掌握链表的翻转是必修课！
什么是链表的翻转:给定链表 head–>4—>3–>2–>1，将其翻转成 head–>1–>2–>3–>4 ，由于翻转链表是如此常见，如此重要，所以我们分别详细讲解下如何用递归和非递归这两种方式来解题.
- 递归翻转
关于递归的文章之前写了三篇，如果之前没读过的，强烈建议点击这里查看，总结了递归的常见解题套路,给出了递归解题的常见四步曲，如果看完对以下递归的解题套路会更加深刻，这里不做赘述了，我们直接套递归的解题思路：
首先我们要查看翻转链表是否符合递归规律：问题可以分解成具有相同解决思路的子问题，子子问题…，直到最终的子问题再也无法分解。
要翻转 head—>4—>3–>2–>1 链表，不考虑 head 结点，分析 4—>3–>2–>1，仔细观察我们发现只要先把 3–>2–>1 翻转成 3<—-2<—-1，之后再把 3 指向 4 即可（如下图示）
图：翻转链表主要三步骤
只要按以上步骤定义好这个翻转函数的功能即可， 这样由于子问题与最初的问题具有相同的解决思路，拆分后的子问题持续调用这个翻转函数即可达到目的。
注意看上面的步骤1，问题的规模是不是缩小了（如下图），从翻转整个链表变成了只翻转部分链表！问题与子问题都是从某个结点开始翻转，具有相同的解决思路，另外当缩小到只翻转一个结点时，显然是终止条件，符合递归的条件！之后的翻转 3–>2–>1, 2–>1 持续调用这个定义好的递归函数即可！
既然符合递归的条件，那我们就可以套用递归四步曲来解题了（注意翻转之后 head 的后继节点变了，需要重新设置！别忘了这一步）
1、定义递归函数,明确函数的功能 根据以上分析，这个递归函数的功能显然是翻转某个节点开始的链表，然后返回新的头结点
/**
* 翻转结点 node 开始的链表
*/
public Node invertLinkedList(Node node) {
}2、寻找递推公式 上文中已经详细画出了翻转链表的步骤，简单总结一下递推步骤如下
- 针对结点 node (值为 4), 先翻转 node 之后的结点 invert(node->next) ,翻转之后 4—>3—>2—>1 变成了 4—>3<—2<—1
- 再把 node 节点的下个节点（3）指向 node，node 的后继节点设置为空（避免形成环），此时变成了 4<—3<—2<—1
- 返回新的头结点，因为此时新的头节点从原来的 4 变成了 1，需要重新设置一下 head
3、将递推公式代入第一步定义好的函数中，如下 (invertLinkedList)
/**
* 递归翻转结点 node 开始的链表
*/
public Node invertLinkedList(Node node) {
if (node.next == null) {
return node;
}
// 步骤 1: 先翻转 node 之后的链表
Node newHead = invertLinkedList(node.next);
// 步骤 2: 再把原 node 节点后继结点的后继结点指向 node，node 的后继节点设置为空(防止形成环)
node.next.next = node;
node.next = null;
// 步骤 3: 返回翻转后的头结点
return newHead;
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
int[] arr = {4,3,2,1};
for (int i = 0; i < arr.length; i++) {
linkedList.addNode(arr[i]);
}
Node newHead = linkedList.invertLinkedList(linkedList.head.next);
// 翻转后别忘了设置头结点的后继结点！
linkedList.head.next = newHead;
linkedList.printList(); // 打印 1，2，3，4
}画外音：翻转后由于 head 的后继结点变了，别忘了重新设置哦！
4、计算时间/空间复杂度 由于递归调用了 n 次 invertLinkedList 函数，所以时间复杂度显然是 O(n), 空间复杂度呢，没有用到额外的空间，但是由于递归调用了 n 次 invertLinkedList 函数，压了 n 次栈，所以空间复杂度也是 O(n)。
递归一定要从函数的功能去理解，从函数的功能看，定义的递归函数清晰易懂，定义好了之后，由于问题与被拆分的子问题具有相同的解决思路，所以子问题只要持续调用定义好的功能函数即可，切勿层层展开子问题，此乃递归常见的陷阱！仔细看函数的功能，其实就是按照下图实现的。(对照着代码看，是不是清晰易懂^_^)
- 非递归翻转链表（迭代解法）
我们知道递归比较容易造成栈溢出，所以如果有其他时间/空间复杂度相近或更好的算法，应该优先选择非递归的解法,那我们看看如何用迭代来翻转链表，主要思路如下
步骤 1：定义两个节点：pre, cur ，其中 cur 是 pre 的后继结点，如果是首次定义， 需要把 pre 指向 cur 的指针去掉，否则由于之后链表翻转，cur 会指向 pre， 就进行了一个环(如下)，这一点需要注意
步骤2：知道了 cur 和 pre,翻转就容易了，把 cur 指向 pre 即可，之后把 cur 设置为 pre ，cur 的后继结点设置为 cur 一直往前重复此步骤即可,完整动图如下
注意：同递归翻转一样，迭代翻转完了之后 head 的后继结点从 4 变成了 1，记得重新设置一下。
知道了解题思路，实现代码就容易多了，直接上代码
/**
* 迭代翻转
*/
public void iterationInvertLinkedList() {
// 步骤 1
Node pre = head;
Node cur = pre.getNext();
pre.setNext(null); // pre 是头结点，避免翻转链表后形成环
// 步骤 2
while (cur != null) {
/**
* 务必注意!!!：在 cur 指向 pre 之前一定要先保留 cur 的后继结点，不然如果 cur 先指向 pre，之后就再也找不到后继结点了
*/
Node next = cur.getNext();
cur.setNext(pre);
pre = cur;
cur = next;
}
// 此时 pre 指向的是原链表的尾结点，翻转后即为链表 head 的后继结点
head.next = pre;
}用迭代的思路来做由于循环了 n 次，显然时间复杂度为 O(n),另外由于没有额外的空间使用，也未像递归那样调用递归函数不断压栈，所以空间复杂度是 O(1),对比递归，显然应该使用迭代的方式来处理！
花了这么大的精力我们总算把翻转链表给搞懂了，如果大家看了之后几道翻转链表的变形，会发现我们花了这么大篇幅讲解翻转链表是值得的。
来源 | 五分钟学算法
作者 | 程序员小吴
