链表

链表相关的典型应用如下：

应用

应用1：Leetocde.21

题目

21. 合并两个有序链表

分析

定义一个虚节点 \(dummy\)，然后开始遍历两个链表，每次将两个链表中较小的节点连接到新链表上，并后移动当前链表的指针。

遍历完后，如果两个链表的长度不相等，将剩余链表直接连接到新链表上。

代码实现

方法一：迭代实现

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        return self.merge(list1, list2)

    def merge(self, left: ListNode, right: ListNode):
        """ 迭代实现 """
        dummy = ListNode(-1)
        node = dummy
        while left and right:
            if left.val < right.val:
                node.next = left
                left = left.next
            else:
                node.next = right
                right = right.next
            node = node.next

        if not left:
            node.next = right
        else:
            node.next = left
        return dummy.next

方法一：递归实现

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        return self.merge(list1, list2)

    def merge(self, left: ListNode, right: ListNode):
        """ 递归实现 """
        if not left:
            return right

        if not right:
            return left

        if left.val < right.val:
            left.next = self.merge(left.next, right)
            return left
        else:
            right.next = self.merge(left, right.next)
            return right

应用2：Leetocde.23

题目

23. 合并 K 个升序链表

分析

方法一：分治

使用分治的思想，将原链表数组拆分，将多个链表的合并，转换为合并两个链表的问题。

方法二：优先级队列

代码实现

把链表的头结点放进一个小根堆，这样堆顶的元素始终是最小的元素，只需要每次弹出一个元素，即最小元素，如果它还有后驱节点，则将其放回小根堆。

方法一：分治

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        return self.merge(lists, 0, len(lists) - 1)

    def merge(self, lists, left: int, right: int):
        if left == right:
            return lists[left]
        if left > right:
            return None

        mid = (left + right) // 2
        return self.merge_2_lists(self.merge(lists, left, mid), self.merge(lists, mid + 1, right))

    def merge_2_lists(self, list1: ListNode, list2: ListNode):
        if list1 is None:
            return list2
        if list2 is None:
            return list1

        dummy = ListNode()
        p = dummy
        p1 = list1
        p2 = list2
        while p1 and p2:
            if p1.val < p2.val:
                p.next = p1
                p1 = p1.next
            else:
                p.next = p2
                p2 = p2.next
            p = p.next
        if p1:
            p.next = p1
        if p2:
            p.next = p2
        return dummy.next

方法二：优先级队列

class Solution {
    ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
            lists.length, (a, b)->(a.val - b.val)
        );

        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            // 如果当前节点还有next节点，将其放回小根堆
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }
}

应用3：Leetocde.141

题目

141. 环形链表

分析

使用快慢指针即可，慢指针走一步，快指针走两步，如果快慢指针相遇，则链表存在环，否则就不存在环。

代码实现

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False

            slow = slow.next
            fast = fast.next.next

        return True

应用4：Leetocde.142

题目

142. 环形链表 II

分析

算法步骤：

• 使用快慢指针 \(slow\) 和 \(fast\)，分别指向链表的头节点；

• 遍历链表，慢指针走一步，快指针走两步，当两者相遇时，则停止遍历；

  • 如果快指针 \(fast\) 指向空节点或者 \(fast\) 的下一个节点为空节点，则不存在环；

  • 否则，重新让慢指针 \(slow\) 指向头节点，\(fast\) 指针从当前位置开始移动，如果两者相遇，则相遇的位置就是环的起点。

代码实现

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

        if (fast == null || fast.next == null) {
            // fast 遇到空指针说明没有环
            return null;
        }

        // 重新指向头结点
        slow = head;
        // 快慢指针同步前进，相交点就是环起点
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

应用5：Leetocde.876

题目

876. 链表的中间结点

分析

使用快慢指针的思路，即慢指针走一步，快指针走两步，当快指针走到链表末尾时，慢指针就指向链表中点。

代码实现

class Solution {
    public ListNode middleNode(ListNode head) {
        // 快慢指针初始化指向 head
        ListNode slow = head, fast = head;
        // 快指针走到末尾时停止
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步
            slow = slow.next;
            fast = fast.next.next;
        }
        // 慢指针指向中点
        return slow;
    }
}

应用6：Leetocde.160

题目

160. 相交链表

分析

代码实现

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        p1 = headA
        p2 = headB
        while p1 != p2:
            p1 = headB if not p1 else p1.next
            p2 = headA if not p2 else p2.next
        return p1

应用7：Leetocde.19

题目

19. 删除链表的倒数第 N 个结点

分析

算法思路：

• 先通过双指针的思路，找到倒数第 \(n + 1\) 个节点，即待删除节点的前一个节点；

  查找倒数的 \(k\) 个节点的思路：

  • 使用两个指针p1和p2，同时指向头节点；

  • 先让 p1 先移动 k 步；

  • 让 p1和p2 同时后移，直到 p1 移动到链表末尾。

• 删除倒数第 \(n + 1\) 个节点的下一个节点；

代码实现

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if not head:
            return head
        dummy = ListNode(-1, head)
        # 找到倒数第n+1个节点
        node = self.findFromEnd(dummy, n + 1)
        node.next = node.next.next
        return dummy.next

    def findFromEnd(self, head: ListNode, k) -> ListNode:
        """ 找到链表的倒数第k个节点 """
        p1 = head
        # p1先移动k步
        for i in range(k):
            p1 = p1.next

        p2 = head
        # p2移动 n - k 步
        while p1:
            p1 = p1.next
            p2 = p2.next
        return p2

    def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:
        dumy = ListNode(-1, head)
        fast, slow = head, dumy

        for i in range(n):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dumy.next

参考：

• 单链表的六大解题套路，你都见过么？

本栏目推荐文章
• 代码随想录算法训练营第二十五天 | 216.组合总和III，17.电话号码的字母组合
• P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III
• SP1716 GSS3 - Can you answer these queries III 题解
• 代码随性训练营第五十天（Python）｜123.买卖股票的最佳时机III 、188.买卖股票的最佳时机IV
• 代码随性训练营第四十八天（Python）｜ 198.打家劫舍、213.打家劫舍II、337.打家劫舍 III
• 普冉PY32系列(十二) 基于PY32F002A的6+1通道遥控小车III - 驱动篇
• 123. 买卖股票的最佳时机 III（难）
• P-III曲线水文频率计算程序（方法）
• 代码训练营第二十五天（Python）｜ 216.组合总和III 、17.电话号码的字母组合
• [vue]精宏技术部试用期学习笔记 III

III题解iii 课程iii 数列iii firefly_iii 路径iii iii offer 32 house-robber-iii 总和216 iii 个数1004 iii 时机 股票123 iii