Singly linked list（单链表）- 2

2021-07-22

1. 单链表

Reference: 递归反转链表的一部分

目标：练习单链表的题目是为了训练递归思维，对递归有个直观的认识。

上篇讲了反转整个链表的递归方法：

找到边界条件：假如只有一个节点，直接返回该节点；
思考 n+1 情况：假如有两个节点，如何进行反转；
思考 n+2 情况：假如有三个节点，如何进行反转；

关键的步骤是：

head.next.next = head (先把尾部和头相连)
head.next = null (重设尾部)
return head.next (新的头部)

这篇文章聊聊如何反转链表的前 N 个节点，以及如何反转链表的 [m, n] 区间节点。

2. 反转链表的前 N 个节点

假定我们有 1 -> 2 -> 3 -> 4 -> 5 这个链表，head = 1，n = 3。

那么我们期望得到的结果是 3 -> 2 -> 1 -> 4 -> 5

和反转整个列表的不同之处在于，n 节点位置 = 之前的尾部，head.next 需要跟 n+1 节点相连。

代码实现

ListNode successor = null; // 后驱节点

// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) { 
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }
    // 以 head.next 为起点，需要反转前 n - 1 个节点
    ListNode last = reverseN(head.next, n - 1);

    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = successor;
    return last;
}

分析

这里引入了 successor 这个变量，也就是 n+1 节点，因为我们反转完了要把新的尾部和这个 n+1 节点连起来。

我们的边界条件从之前的 head.next == null 改成了 n = 1，因为 n = 1 意味着我们已经到了最后一个节点。

递归语句则需要把 n 的值进行递减。

实际的操作和之前一样，尾部和头部相连，重设尾部节点（head.next = successor)。

注意 successor 的初始值是 null，但是当 n = 1 的时候我们会给这个变量赋值，确保最后一次「归」的时候能顺利连起来。

假定我们有 1 -> 2 -> 3 -> 4 -> 5 这个链表，head = 1，n = 3。

在这个例子里面，4 就是 successor，n = 1 的情况就是 head = 1 的时候（因为我们已经把 1-2-3 反转成 3-2-1 了）。

head.next = successor

翻译一下就是：1.next = 4

3. 反转一个区间的链表

代码

PS: 这里我们需要跟上一部分的代码加在一起哦！~

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

分析

假如 m = 1，就是刚才分析过的那种题目，反转前 n 个节点，所以直接调用刚才那个 function。

假如 m 大于 1，我们在进行首尾相连的时候就不能直接 head.next.next = head 了，因为 head 是链表的第一个节点，而 m 不等于 1。

因此，我们需要先移动 head 并且同步减少 m 和 n 的值，当 m = 1 的时候，这个 head 才是真正需要反转的区间的 head。

也就是 head.next = reverseBetween(head.next, m - 1, n - 1); 这行代码所做的事情。

当 m = 1 了，我们还是使用之前的那个 reverseN function。

所以实际的逻辑还是在 reverseN 里面，reverseBetween 最重要的作用就是找到真正的 head。

4. 结语

接下来要学的是如何k个一组反转链表，也是跟链表相关的。

Luna Tech