【LeetCode刷题日记】：反转链表（面试基础考察）

反转链表：

题目背景：LeetCode206

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

双指针解法：

/ 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

题目解析： 如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。 其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:

我们只需要改变链表的next指针指向： 首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。不然会导致数据丢失， 为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

我们把cur的指向改变，指向pre，然后我们分别继续移动这两个指针，cur的位置给pre，temp的位置给cur，都相当于是向后移动一次 为什么先移动pre，而不是先移动cur，如果是先移动cur，那么cur的值就被temp覆盖了，pre的位置就改变不了了。

递归解法：

// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

解法解析：

递归的逻辑就是双指针的逻辑，，只是写起来的代码更简单些，

在这里我们定义了两个方法，为什么需要两个方法，因为我们要实现递归，需要传递两个参数pre cur，但是题目只给出了一个head，因此reverseList(head) 负责启动递归，里面调用 reverse(null, head)，真正递归逻辑在 reverse(prev, cur) 里。

具体流程：

假设原链表：

plaintext

1 → 2 → 3 → 4 → 5 → null

初始调用

reverseList(head);

进入：

reverse(null, 1);

此时：

plaintext

prev = null
cur  = 1

第 1 层递归：reverse (null, 1)

1. temp = cur.next = 2
2. cur.next = prev → 1 → null
3. 递归调用：reverse(1, 2)

链表现在：

plaintext

null ← 1   2 → 3 → 4 → 5 → null

第 2 层递归：reverse (1, 2)

1. temp = 3
2. cur.next = 1 → 2 → 1
3. 调用：reverse(2, 3)

plaintext

null ← 1 ← 2   3 → 4 → 5 → null

第 3 层递归：reverse (2, 3)

1. temp = 4
2. 3 → 2
3. 调用：reverse(3,4)

plaintext

null ← 1 ← 2 ← 3   4 →5 →null

第 4 层递归：reverse (3,4)

1. temp =5
2. 4→3
3. 调用：reverse(4,5)

第 5 层递归：reverse (4,5)

1. temp = null
2. 5→4
3. 调用：reverse(5, null)

plaintext

null ←1 ←2 ←3 ←4 ←5

最后一层：cur == null，开始返回

java

运行

if (cur == null) return prev;

这里 prev 是 5

然后一层层返回 5 → 最终回到 reverseList

返回 5，链表反转完成！

总结：递归就是每次改变循环的位置，替代循环！

reverse 就是：

1. 保存下一个节点
2. 把当前节点指向前一个
3. 递归往后走
4. 走到 null 时，prev 就是新头节点

当前节点指向前一个，然后递归下一组，直到走到头，最后那个节点就是新头。