算法思维训练（三）| 链表🎓-工具盒子

一、链表基础知识 {#一-链表基础知识}

1. 链表概念 {#1--链表概念}

链表是一种常见的基础数据结构。在链表中，每个节点包含指向下一个节点的指针，这些指针把节点连接成链状结构。

2. 哨兵节点 {#2--哨兵节点}

哨兵节点是为了简化处理链表边界条件而引入的附加链表节点。哨兵节点通常位于链表的头部，它的值没有任何意义，他可以简化代码的逻辑（非代码效率），如节点判空或头节点值判断等逻辑不需要再单独编写。在一个有哨兵节点的链表中，从第2个节点开始才真正保存有意义的信息。

二、链表知识扩展 {#二-链表知识扩展}

1. 链表中的双指针 {#1--链表中的双指针}

前后双指针：寻找链表中倒数第 i个元素，可以通过右指针先移动 i-1次后，左右指针一起移动，直到右指针到达最右侧，左指针所指向的节点即倒数第 i个元素。
快慢指针：左右指针以不同的速度向后移动，右指针如果左指针移动速度的两倍，当右指针到达最右侧时，左指针刚好处于中间位置。

链表题目 | 双指针 {#链表题目---双指针}

题目一：删除倒数第k个节点 {#题目一-删除倒数第k个节点}

如果给定一个链表，请问如何删除链表中的倒数第 k个节点？假设链表中节点的总数为 n，那么 1≤k≤n。要求只能遍历链表一次。例如，输入 图4.1(a)中的链表，删除倒数第 2个节点之后的链表如 图4.1(b)所示。

题目分析 {#题目分析}

难度： ⭐
思路： 典型的前后双指针题目，在右指针移动到最右侧时，删除左指针的元素即可。

参考代码 {#参考代码}

Tips：2023-11-14 10:22 {#Tips-2023-11-14-10-22}

题目二：链表中环的入口节点 {#题目二-链表中环的入口节点}

如果一个链表中包含环，那么应该如何找出环的入口节点？从链表的头节点开始顺着 next指针方向进入环的第 1个节点为环的入口节点。例如，在如 图4.3所示的链表中，环的入口节点是节点 3。

题目分析 {#题目分析-}

难度： ⭐⭐
思路： 题目可通过结合双指针的两种使用方式实现目的。
解法一，将问题拆分为三个子问题：
1. 是否存在环链：快指针以慢制作的两倍速度移动，如果快慢指针相遇，则说明存在环。
2. 确定环节点长度 m：快慢指针相遇的节点一定在环内，以该节点起，遍历下一个节点，当再次遍历到该节点，中间经过的节点数即环的长度。
3. 获取链倒数第 m个元素：通过前后双指针获取倒数第 m个节点元素。
解法二，基于解法一，省去获取环节点数的步骤：
通过仔细分析，不难发现并没有必要求得环中节点的数目。如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了 k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了 2k步。因此，到相遇时快的指针比慢的指针多走了 k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数 k一定是环中节点的数目的整数倍，此时慢的指针走过的步数 k也是环中节点数的整数倍。
此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了 k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了 k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。

参考代码 {#参考代码-}

public ListNode entryNodeOfLoop(ListNode pHead) {
    ListNode slow = pHead;
    ListNode fast = pHead;
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode temp = slow;
            while(pHead != temp) {
                pHead = pHead.next;
                temp = temp.next;
            }
            return temp;
        }
    }
    return null;
}

Tips：2024-01-21 01:01 {#Tips-2024-01-21-01-01}

题目三：两个链表的第1个重合节点 {#题目三-两个链表的第1个重合节点}

输入两个单向链表，请问如何找出它们的第 1个重合节点。例如，图4.5中的两个链表的第 1个重合节点的值是 4。

题目分析 {#题目分析--}

难度： ⭐
思路： 根据链表的特性，不难发现，在节点重合后不可能在分叉，即链表起点可能不一样，但重点绝对一样。可以以两链表的长度差为前后双指针距离差，左指针指向长的链首节点，右指针从短链首节点，左指针移动长度差距离后，左右指针开始一起移动，当左右指针指向的值为同一个的时候，所指向的节点即为所求。

参考代码 {#参考代码--}

public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    while (p1 != p2) {
        p1 = p1 == null ? pHead2 : p1.next;
        p2 = p2 == null ? pHead1 : p2.next;
    }
    return p1;
}

Tips：2024-01-21 01:02 {#Tips-2024-01-21-01-02}

2. 反转链表 {#2--反转链表}

单项链表最大的特点就是其单向性，只能单向遍历，有时在处理部分问题时，将链表反转（首尾依次交换）后会更加的容易解决。而如何反转链表，也是一类常见的问题。

链表题目 | 反转链表 {#链表题目---反转链表}

题目一：反转链表 {#题目一-反转链表}

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。例如，把 图4.8(a)中的链表反转之后得到的链表如 图4.8(b)所示。

题目分析 {#题目分析---}

难度： ⭐
思路： 反转，即将节点指向下一个节点的指针指向上一个节点，但由于修改指向后，下一个节点会丢失，所以可以使用一个临时变量存储下一个节点。假如当前已经处理到第 j个节点，i是其上一个节点，k是其下一个节点，此时用一个临时节点保存 k节点，然后将 j节点指向 i节点，最后又对临时节点进行想同处理，直到不再有下一个节点为止。

参考代码 {#参考代码---}

public ListNode reverseList (ListNode head) {
    ListNode newNode = null;
    while (head != null) {
        ListNode temp = head.next;
        head.next = newNode;
        newNode = head;
        head = temp;
    }
    return newNode;
}

Tips：2024-01-21 01:03 {#Tips-2024-01-21-01-03}

题目二：链表中的数字相加 {#题目二-链表中的数字相加}

给定两个表示非负整数的单向链表，请问如何实现这两个整数的相加并且把它们的和仍然用单向链表表示？链表中的每个节点表示整数十进制的一位，并且头节点对应整数的最高位数而尾节点对应整数的个位数。例如，在 图4.10(a)和 图4.10(b)中，两个链表分别表示整数 123和 531，它们的和为 654，对应的链表如图 4.10(c)所示。

题目分析 {#题目分析----}

难度： ⭐
思路： 题目容易忽略的问题是进位以及两链表长度不同时，应按位加（倒序），步骤如下：
1. 将两个链表反转，反转后的链表；
2. 从首节点开始依次做加法运算，进位记录到临时变量中，下一节点进行运算时将进位也加入到运算并清除变量；
3. 将运算结果链表反转。

参考代码 {#参考代码----}

Tips：2024-01-21 01:04 {#Tips-2024-01-21-01-04}

题目三：重排链表 {#题目三-重排链表}

给定一个链表，链表中节点的顺序是 L0 → L1 → L2 → ... → Ln-1 → Ln，请问如何重排链表使节点的顺序变成 L0 → Ln → L1 → Ln-1→ L2 → Ln-2 → ...？例如，输入图 4.12(a)中的链表，重排之后的链表如图 4.12(b)所示。

题目分析 {#题目分析-----}

难度： ⭐
思路： 通过观察不难发现，所求链表的元素即按首尾依次各取一个元素放入新的链表中，剩余的元素重复该操作，直到操作次数达到链表长度的一半为止。所以可以通过将链表反转，通过原链表和反转后的链表依次取值，直到到达链表的中心点为止（在反转的过程中记录下链表的长度，避免重复遍历）。

参考代码 {#参考代码-----}

Tips：2024-01-21 01:05 {#Tips-2024-01-21-01-05}

题目四：回文链表 {#题目四-回文链表}

如何判断一个链表是不是回文？要求解法的时间复杂度是 O(n)，并且不得使用超过 O(1)的辅助空间。如果一个链表是回文，那么链表的节点序列从前往后看和从后往前看是相同的。例如 图4.13中的链表的节点序列从前往后看和从后往前看都是 1、2、3、3、2、1，因此这是一个回文链表。

题目分析 {#题目分析------}

难度： ⭐⭐
思路： 如果不考虑 O(1)辅助空间的限制，那么将链表反转后，使用一个 O(n)的辅助控件进行存储，再和原链表一一进行比较即可。开了到到辅助空间的限制，可以直接对原链表进行反转，但不完全反转链表。首先遍历一次获取链表长度，随后对原链表进行反转，在反转到一半的时候停止，此时左右节点同时忘两边遍历，一一比较即可，需要注意的是奇数和偶数两次情况的处理略有不同

参考代码 {#参考代码------}

Tips：2024-01-21 01:06 {#Tips-2024-01-21-01-06}

3. 双向链表和循环链表 {#3--双向链表和循环链表}

（待补充）

链表题目 | 双向链表和循环链表 {#链表题目---双向链表和循环链表}

题目一：展平多级双向链表 {#题目一-展平多级双向链表}

在一个多级双向链表中，节点除了有两个指针分别指向前后两个节点，还有一个指针指向它的子链表，并且子链表也是一个双向链表，它的节点也有指向子链表的指针。请将这样的多级双向链表展平成普通的双向链表，即所有节点都没有子链表。例如，图4.14(a)所示是一个多级双向链表，它展平之后如 图4.14(b)所示。

题目分析 {#题目分析-------}

难度： ⭐
思路： 根据题意，可以注意到，这是一个比较经典的递归问题；当发现节点存在其他链的指针时，暂存下一个节点数据，通过递归的方式处理其他链的数据。在所有的链都处理完后，再将处理好的节点继续只想上一步暂存的节点即可。

参考代码 {#参考代码-------}

Tips：2024-01-21 01:07 {#Tips-2024-01-21-01-07}

题目二：排序的循环链表 {#题目二-排序的循环链表}

在一个循环链表中节点的值递增排序，请设计一个算法在该循环链表中插入节点，并保证插入节点之后的循环链表仍然是排序的。例如，图4.15(a)所示是一个排序的循环链表，插入一个值为4的节点之后的链表如 图4.15(b)所示。

题目分析 {#题目分析--------}

难度： ⭐
思路： 遍历节点时，如果下一个节点和当前节点是顺序的，只需要判断是否满足新值在其中见即可；如果不是顺序的，判断是否满足值大于当前节点或者小于下一个节点即可；需要注意的是，存在特殊情况，即链表只存在一个节点或者是空链表。

参考代码 {#参考代码--------}

Tips：2024-01-21 01:08 {#Tips-2024-01-21-01-08}

4. 附加题目 {#4--附加题目}

题目一：删除链表中重复的结点 {#题目一-删除链表中重复的结点}

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 处理后为 1 -> 2 -> 5。

题目分析 {#题目分析---------}

难度： ⭐⭐
思路： 方案一，比较相邻节点，重复节点依次跳过即可；方案二，记录上一个节点，并通过Map或者Set记录节点值，后续节点值如果在Map或Set中存在，则跳过，直到值不再一样，令上一个节点指向当前节点。

参考代码 {#参考代码---------}

public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null) {
        return null;
    }
    ListNode res = new ListNode(0);
    ListNode head = res;
    head.next = pHead;

    while(head.next != null &amp;&amp; head.next.next != null) {
        if (head.next.val == head.next.next.val) {
            int temp = head.next.val;
            while (head.next != null &amp;&amp; temp == head.next.val) {
                head.next = head.next.next;
            }
        } else {
            head = head.next;
        }
    }

    return res.next;



`}
`

Tips：2024-09-09 11:07 {#Tips-2024-09-09-11-07}

题目二：复杂链表的复制 {#题目二-复杂链表的复制}

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出。

题目分析 {#题目分析----------}

难度： ⭐⭐⭐
思路： 题目的难点在于每个节点的随机节点不太好处理。此处可以考虑使用Map记录节点和拷贝节点的关系，或者插入拷贝节点的方式进行处理。
解法一，Map映射：
1. 建立哈希表，key为原始链表的节点，value为拷贝链表的节点；
2. 遍历原始链表，依次拷贝每个节点，并连接指向后一个的指针，同时将原始链表节点与拷贝链表节点之间的映射关系加入哈希表；
3. 遍历哈希表，对于每个映射，拷贝节点的ramdom指针就指向哈希表中原始链表的random指针
解法二，插入拷贝节点：
1. 遍历链表，对每个节点新建一个拷贝节点，并插入到该节点之后；
2. 使用双指针再次遍历链表，两个指针每次都移动两步，一个指针遍历原始节点，一个指针遍历拷贝节点，拷贝节点的随机指针跟随原始节点，指向原始节点随机指针的下一位；
3. 再次使用双指针遍历链表，每次越过后一位相连，即拆分成两个链表。

参考代码 {#参考代码----------}

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }




}\*/

`public RandomListNode clone(RandomListNode pHead) {
// 空节点直接返回
if (pHead == null) {
return pHead;
}
// 添加一个头部节点
RandomListNode res = new RandomListNode(0);
// 哈希表，key为原始链表的节点，value为拷贝链表的节点
HashMap<RandomListNode, RandomListNode> mp = new HashMap<>();
RandomListNode cur = pHead;
RandomListNode pre = res;
// 遍历原始链表，开始复制
while (cur != null){
// 拷贝节点
RandomListNode clone = new RandomListNode(cur.label);
// 用哈希表记录该节点下的拷贝节点
mp.put(cur, clone);
// 连接
pre.next = clone;
pre = pre.next;
// 遍历
cur = cur.next;
}
// 遍历哈希表
for (HashMap.Entry<RandomListNode, RandomListNode> entry : mp.entrySet()){
// 原始链表中random为空
if (entry.getKey().random == null) {
entry.getValue().random = null;
}
else {
// 将新链表的random指向哈希表中原始链表的random
entry.getValue().random = mp.get(entry.getKey().random);
}
}
// 返回去掉头
return res.next;
}
`