算法思维训练（三）| 链表🎈

一、链表基础知识

1. 链表概念

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

2. 哨兵节点

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

3. 本章题目节点类

Ⅰ. 单向节点

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {
        this.val = x;
    }
}

Ⅱ. 三向节点

public class TripListNode {
    public int val;
    public TripListNode last;
    public TripListNode next;
    public TripListNode child;
    public TripListNode(int val) {
        this.val = val;
    }
}

Ⅲ. 随机双向节点

public class RandomListNode {
    public int label;
    public RandomListNode next = null;
    public RandomListNode random = null;
    public RandomListNode(int label) {
        this.label = label;
    }
}

---

二、链表知识扩展

1. 链表中的双指针

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

链表题目 | 双指针

题目一：删除倒数第k个节点

题目描述

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

题目分析

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

参考代码

public void deleteNode(ListNode head, int index) {
    if (index <= 0) {
        return;
    }
    int count = 1;
    ListNode temp = null;
    while (count++ < index) {
        temp = head;
        head = head.next;
    }
    if (temp == null) {
        ListNode next = head.next;
        head.val = next.val;
        head.next = next.next;
    } else if (head != null) {
        temp.next = head.next;
    }
}

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

---

题目三：两个链表的第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

---

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

---

题目二：链表中的数字相加

题目描述

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

题目分析

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

参考代码

public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
    // 利用輔助空間處理
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    ListNode res = null;
    // 将两个链表的数据依次放入栈
    while (head1 != null) {
        stack1.push(head1.val);
        head1 = head1.next;
    }
    while (head2 != null) {
        stack2.push(head2.val);
        head2 = head2.next;
    }
    // 使stack1始终为最长的栈
    if (stack1.size() < stack2.size()) {
        Stack<Integer> temp = stack1;
        stack1 = stack2;
        stack2 = temp;
    }
    int carry = 0;
    // 对栈元素进遍历，并记录进位
    while (!stack1.isEmpty()) {
        int val;
        if (stack2.isEmpty()) {
            // 短栈元素空了，以长栈元素为准
            val = stack1.pop() + carry;
        } else {
            // 通常情况下计算两数和，计算进位和余位
            val = stack1.pop() + stack2.pop() + carry;
            if (val > 9) {
                carry = 1;
                val %= 10;
            } else {
                carry = 0;
            }
        }
        // 建立节点，并赋予给定义的头节点res
        ListNode newNode = new ListNode(val);
        newNode.next = res;
        res = newNode;
    }

    // 如果还有进位，则将进位作为一个新的节点再赋予头节点
    if (carry > 0) {
        ListNode newNode = new ListNode(carry);
        newNode.next = res;
        res = newNode;
    }
    return res;
}

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) 所示。

题目分析

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

参考代码

public void reorderList(ListNode head) {
    // 使用栈记录节点元素
    Stack<ListNode> stack = new Stack<>();
    ListNode temp = head;
    while (head != null) {
        stack.push(head);
        head = head.next;
    }

    int size = stack.size();
    int limit = size / 2;

    // 定义一个临时节点
    head = new ListNode(0);
    for (int i = 0; i < limit; i++) {
        // 取左边节点
        head.next = temp;
        temp = temp.next;

        // 取右边节点
        ListNode pop = stack.pop();
        pop.next = null;
        head.next.next = pop;

        // 推进节点
        head = head.next.next;
    }

    // 如果是奇数，最后需要将最中间的节点加上
    if (size % 2 != 0) {
        temp.next = null;
        head.next = temp;
    }
}

Tips：2024-01-21 01:05

---

题目四：回文链表

题目描述

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

题目分析

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

参考代码

public boolean isPalindrome(ListNode head) {
    int len = 0;
    ListNode temp = head;
    // 先统计链表长度
    while (temp != null) {
        len++;
        temp = temp.next;
    }

    // 在长度 2 以下，只有长度是 1 时是回文链表
    if (len < 2) {
        return len == 1;
    }

    // 将前一般的元素进行反转，后一半的元素和前一半元素进行依次比较
    int middle = len / 2;
    // last 标记上一个节点，head标记当前节点
    int count = 1;
    ListNode last = head;
    head = head.next;
    // 清除上一个节点的 next 指向
    last.next = null;
    while (head != null) {
        // 前一半反转
        if (count++ < middle) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        } else {
            // 停止反转时判断，是否需要后移；元素位号是后一半的第一个元素，即 middle + 1 时判断
            if (count == (middle + 1)) {
                // 如果长度为奇数，那么head需要后移一位
                head = len % 2 == 0 ? head : head.next;
            }
            // 后一半比较
            if (last == null || last.val != head.val) {
                return false;
            }
            last = last.next;
            head = head.next;
        }
    }

    return true;
}

Tips：2024-01-21 01:06

---

3. 双向链表和循环链表

• （待补充）

链表题目 | 双向链表和循环链表

题目一：展平多级双向链表

题目描述

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

题目分析

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

参考代码

public TripListNode spreadNode(TripListNode head) {
    TripListNode temp = head;
    while (temp != null) {
        spreadChileNode(temp);
        temp = temp.next;
    }
    return head;
}

public void spreadChileNode(TripListNode node) {
    TripListNode child = node.child;
    if (child != null) {
        // 清除分支子节点,并将分支子节点上一个节点指针指向当前节点
        node.child = null;
        child.last = node;
        // 记录下一个节点，并将当前节点下一个节点指针指向分支子节点
        TripListNode next = node.next;
        node.next = child;
        // 遍历分支子节点，处理子节点的所有子节点
        while (child.next != null) {
            child = child.next;
            if (child.child != null) {
                spreadChileNode(child);
            }
        }
        // 分支子节点的下一个节点指针指向提前记录的 next 节点，同时更新上一个节点指针
        child.next = next;
        next.last = child;
    }
}

Tips：2024-01-21 01:07

---

题目二：排序的循环链表

题目描述

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

题目分析

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

参考代码

public ListNode addListNode(ListNode head, int val) {
    if (head == null) {
        // 空节点时构建节点
        head = new ListNode(val);
        head.next = head;
    } else if (head.next == head) {
        // 单节点时插入节点
        ListNode newNode = new ListNode(val);
        head.next = newNode;
        newNode.next = head;
    } else {
        // 超过单个节点时插入
        addNode(head, val);
    }
    return head;
}

public void addNode(ListNode head, int val) {
    ListNode first = head;
    ListNode next = head.next;
    // 记录应该插入节点位置
    // 新节点大于所有元素，则在最靠右最大值节点后插入；否则应该在找到的节点后插入；
    ListNode insertNode = head;
    while (head.next != first) {
        // 新值在 head 和 next 之间时插入元素
        if (head.val <= val && next.val >= val) {
            // 找到位置更新 insertNode 为正确位置并停止遍历，否则继续
            insertNode = head;
            break;
        } else {
            // 没找到位置，继续记录最靠右的最大值节点
            if (head.val >= insertNode.val) {
                insertNode = head;
            }
            head = next;
            next = next.next;
        }
    }

    ListNode newNode = new ListNode(val);
    ListNode temp = insertNode.next;
    insertNode.next = newNode;
    newNode.next = temp;
}

Tips：2024-01-21 01:08

---

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 && head.next.next != null) {
        if (head.next.val == head.next.next.val) {
            int temp = head.next.val;
            while (head.next != null && temp == head.next.val) {
                head.next = head.next.next;
            }
        } else {
            head = head.next;
        }
    }

    return res.next;
}

Tips：2024-09-09 11:07

---

题目二：复杂链表的复制

题目描述

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

题目分析

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

参考代码

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;
}

Tips：2024-09-11 16:51

三、章节小结

  略

---