Luna Tech

Tutorials For Dummies.

Singly linked list(单链表)- 2

2021-07-22


1. 单链表

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

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

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

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

关键的步骤是:

  1. head.next.next = head (先把尾部和头相连)
  2. head.next = null (重设尾部)
  3. 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)。

假定我们有 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. 反转一个区间的链表

相关题目

92.反转链表

最后,我们来看一下如果给定 m 和 n,如何只反转这个区间的节点。

Note: 第一个节点的 index = 1 而不是 0.

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

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

代码

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个一组反转链表,也是跟链表相关的。