链表专题¶

本文件按 核心技术模块 组织，而非按题号。每个模块内由浅入深，相同模块内的变量命名严格统一，便于形成模式记忆。

---

第 0 章 · 链表编程的三大支柱¶

链表没有索引，一切操作都靠指针完成。掌握下面三条原则，80% 的链表题都有稳定套路。

支柱 1 · 关键节点必须用变量保留¶

链表是一条单向的"引用链"，丢掉一个节点的引用就等于丢掉它之后的整条链。任何"之后还会用到的节点"都必须提前用变量捕获——尤其是链表头。

支柱 2 · 指针改写前先暂存 next¶

当你要把 cur.next 指向别处时，原来的 cur.next 就丢了。所有反转 / 交换题都要先 nxt = cur.next，再修改指针。这是条件反射，不是需要思考的步骤。

支柱 3 · Dummy 节点消除"头节点特殊性"¶

---

两个最容易卡住的疑惑点¶

疑惑 1：反转链表里，为什么初始 pre = None？¶

反转后的链表，原头节点会变成新尾节点，而合法链表的尾节点 next 必须是 None。第一轮循环干的事是把原头节点的 next 指向 pre，所以 pre 必须提前就是 None。

如果写成 pre = head，第一轮就会 head.next = head，形成自环。

pre 不是"前一个节点"那么抽象，它是"当前节点反转后应该指向谁"的那个指针。初始时链表第一个节点反转后应该指向 None，所以 pre 初始化为 None。

疑惑 2：Dummy 节点到底是干嘛的？"便于处理"太模糊了¶

Dummy 的真正作用只有一句话：当结果链表的头节点在算法执行前不确定时，dummy.next 给你一个稳定的返回入口。

• 合并两个链表：新链表的头可能是 L1 也可能是 L2，执行前不确定 → 用 dummy
• 删除倒数第 N 个：要删的可能就是头节点 → 用 dummy
• K 个一组反转：每组反转后头都会变 → 用 dummy

额外能力：K 组反转中 dummy 不仅是返回入口，p0 = dummy 还承担了"每组反转前的前驱指针"的角色，用来把上一段链表和反转后的新头连起来。这两个能力是叠加的。

判断标准极简：结果链表的头节点在执行前是否确定？不确定就用 dummy。

第 1 章 · 链表节点定义与调试工具¶

后续所有章节共用下面的 ListNode。show_chain 是调试利器，避免每次手动打印。

In [2]:

from typing import Optional, List

class ListNode:
    def __init__(self, val: int = 0, next: "Optional[ListNode]" = None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"ListNode({self.val})"

    def show_chain(self):
        vals, cur = [], self
        while cur:
            vals.append(str(cur.val))
            cur = cur.next
        return " -> ".join(vals) + " -> None"


def build(vals: List[int]) -> Optional[ListNode]:
    # 快速从列表构造链表，仅用于测试
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


# 演示
head = build([1, 2, 3])
print(head.show_chain())

from typing import Optional, List class ListNode: def __init__(self, val: int = 0, next: "Optional[ListNode]" = None): self.val = val self.next = next def __repr__(self): return f"ListNode({self.val})" def show_chain(self): vals, cur = [], self while cur: vals.append(str(cur.val)) cur = cur.next return " -> ".join(vals) + " -> None" def build(vals: List[int]) -> Optional[ListNode]: # 快速从列表构造链表，仅用于测试 dummy = ListNode() cur = dummy for v in vals: cur.next = ListNode(v) cur = cur.next return dummy.next # 演示 head = build([1, 2, 3]) print(head.show_chain())

1 -> 2 -> 3 -> None

第 2 章 · 反转操作模块¶

统一变量命名：pre / cur / nxt。所有反转题共用这套名字。

这一章从最基础的整链反转开始，逐步扩展到：

• 整链反转：206 反转链表
• 反转作为子步骤：234 回文链表
• 区间反转：92 反转链表 II（指定区间翻转）
• 分组反转：24 两两交换、25 K 个一组反转

核心公式永远是这三行：

nxt = cur.next    # 支柱 2：先暂存
cur.next = pre    # 反转当前指针
pre = cur; cur = nxt  # 整体右移一格

2.1 三指针反转模板 · 206 反转链表¶

给你单链表的头节点，反转链表并返回新头。

模块归属：反转。

核心：维护 pre、cur 两个相邻指针，循环结束时 pre 恰好指向原尾节点（即新头），cur 指向下一个区间的头结点或者None； 这点很重要，在后续，需要连接两个区间的时候，就需要根据这个性质

为什么 pre 初始化为 None：见第 0 章「疑惑 1」。

In [3]:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre   # cur 已到 None，pre 即新头


head = build([1, 2, 3, 4])
print(Solution().reverseList(head).show_chain())

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre, cur = None, head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre # cur 已到 None，pre 即新头 head = build([1, 2, 3, 4]) print(Solution().reverseList(head).show_chain())

4 -> 3 -> 2 -> 1 -> None

2.2 反转作为子步骤 · 234 回文链表¶

判断链表是否是回文。要求 O(1) 空间。

模块归属：反转 + 快慢指针。 三步走：

1. 快慢指针找中点（3.1 节模板）
2. 反转后半段（复用 2.1）
3. 前后半段逐位比较

为什么反转后半段对比即可？因为回文的前半段 = 反转后的后半段（如果链表是回文）。比较时只需遍历较短的那一半，即反转后的段（奇数长度时中点单独处理，刚好 slow 落在正中心或下中点）。

In [4]:

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        mid = self.middleNode(head)
        head2 = self.reverseList(mid)
        # 反转段可能不长于前半段，以 head2 结束为准
        while head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True


print(Solution().isPalindrome(build([1, 2, 2, 1])))    # True
print(Solution().isPalindrome(build([1, 2, 3, 2, 1]))) # True
print(Solution().isPalindrome(build([1, 2, 3])))       # False

class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre, cur = None, head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre def isPalindrome(self, head: Optional[ListNode]) -> bool: mid = self.middleNode(head) head2 = self.reverseList(mid) # 反转段可能不长于前半段，以 head2 结束为准 while head2: if head.val != head2.val: return False head = head.next head2 = head2.next return True print(Solution().isPalindrome(build([1, 2, 2, 1]))) # True print(Solution().isPalindrome(build([1, 2, 3, 2, 1]))) # True print(Solution().isPalindrome(build([1, 2, 3]))) # False

True
True
False

2.3 区间反转 · 92 反转链表 II¶

反转从位置 left 到位置 right 的子链表（1-indexed）。

模块归属：反转（区间版）。 思路：

1. 走到 left 的前驱 p0（用 dummy 防止 left=1 时头节点变化）
2. 从 left 处开始反转 right - left + 1 个节点（复用 2.1 的三指针）
3. 反转结束后：
   • p0.next（原 left 位置节点）现在是区间尾 → 连到剩余链表
   • p0.next 更新为区间新头（即 pre）

这正是 K 组反转的单组版，是 25 题的简化前置。

In [5]:

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 前置设置
        dummy = ListNode(next=head)
        p0 = dummy  # 为了找到反转后的尾节点
        for _ in range(left - 1):
            p0 = p0.next
        cur = p0.next  # 遍历开始的地方

        # 单组反转
        pre = None
        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt

        # 拼接：p0.next 原本指向区间首（反转后变成区间尾）
        trail = p0.next
        trail.next = cur  # 连接下一段的头节点
        p0.next = pre     # 更新区间的新头节点，pre为反转后的头节点
        return dummy.next


print(Solution().reverseBetween(build([1, 2, 3, 4, 5]), 2, 4).show_chain())
# 1 -> 4 -> 3 -> 2 -> 5

class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: # 前置设置 dummy = ListNode(next=head) p0 = dummy # 为了找到反转后的尾节点 for _ in range(left - 1): p0 = p0.next cur = p0.next # 遍历开始的地方 # 单组反转 pre = None for _ in range(right - left + 1): nxt = cur.next cur.next = pre pre = cur cur = nxt # 拼接：p0.next 原本指向区间首（反转后变成区间尾） trail = p0.next trail.next = cur # 连接下一段的头节点 p0.next = pre # 更新区间的新头节点，pre为反转后的头节点 return dummy.next print(Solution().reverseBetween(build([1, 2, 3, 4, 5]), 2, 4).show_chain()) # 1 -> 4 -> 3 -> 2 -> 5

1 -> 4 -> 3 -> 2 -> 5 -> None

2.4 固定组反转 · 24 两两交换¶

两两交换相邻节点。

模块归属：反转（k=2 特例）+ Dummy。 变量约定：

• p0：当前这一对的前驱（上一对的尾，或 dummy）
• node1, node2：当前这一对
• node3：下一对的起点

交换后 p0 → node2 → node1 → node3，然后 p0 移到 node1，继续下一对。

In [6]:

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # 前置设置
        dummy = ListNode(next=head)
        p0 = dummy
        cur = head

        # 循环反转
        while p0.next and p0.next.next:
            # 标准反转循环，翻转 2 个节点，注意存在多个反转的时候，需要将pre至于while内，每一次都需要变为None
            pre= None
            for _ in range(2):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt

            # 拼接：p0.next 原本是区间首（反转后变成区间尾）
            trail = p0.next
            trail.next = cur      # 区间尾 → 接下一段
            p0.next = pre         # p0 → 指向区间新头
            p0 = trail            # trail 作为下一对的前驱

        return dummy.next


print(Solution().swapPairs(build([1, 2, 3, 4])).show_chain())  # 2 -> 1 -> 4 -> 3
print(Solution().swapPairs(build([1, 2, 3])).show_chain())     # 2 -> 1 -> 3

class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: # 前置设置 dummy = ListNode(next=head) p0 = dummy cur = head # 循环反转 while p0.next and p0.next.next: # 标准反转循环，翻转 2 个节点，注意存在多个反转的时候，需要将pre至于while内，每一次都需要变为None pre= None for _ in range(2): nxt = cur.next cur.next = pre pre = cur cur = nxt # 拼接：p0.next 原本是区间首（反转后变成区间尾） trail = p0.next trail.next = cur # 区间尾 → 接下一段 p0.next = pre # p0 → 指向区间新头 p0 = trail # trail 作为下一对的前驱 return dummy.next print(Solution().swapPairs(build([1, 2, 3, 4])).show_chain()) # 2 -> 1 -> 4 -> 3 print(Solution().swapPairs(build([1, 2, 3])).show_chain()) # 2 -> 1 -> 3

2 -> 1 -> 4 -> 3 -> None
2 -> 1 -> 3 -> None

2.5 通用 K 组反转 · 25 K 个一组反转¶

每 k 个一组翻转链表，不足 k 个保持原序。

模块归属：反转（k 通用）+ Dummy。 变量约定（延续 2.4）：

• p0：当前组前驱（dummy 开始，每组结束后更新）
• pre / cur / nxt：组内反转用的三指针
• trail：组头变量（反转前是组头，反转后变成组尾）—— 这是整道题最关键的变量，它承担了"把本组连向下一组"的任务

流程：先数总长 n，每当 n >= k 就反转一组。反转完后：

• trail = p0.next（组头，反转后变组尾）
• trail.next = cur（组尾连到下一组起点）
• p0.next = pre（上一段连到本组新头）
• p0 = trail（下一组的前驱 = 本组组尾）

In [7]:

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 计算链表长度
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next

        # 前置设置
        dummy = ListNode(next=head)
        p0 = dummy
        cur = head

        # 循环反转
        while n >= k:
            n -= k
            pre = None
            for _ in range(k):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt

            trail = p0.next      # 组头 → 反转后变组尾
            trail.next = cur     # 连向下一组
            p0.next = pre        # 上一段连向新组头
            p0 = trail           # 推进组前驱
        return dummy.next


print(Solution().reverseKGroup(build([1, 2, 3, 4, 5]), 2).show_chain())
# 2 -> 1 -> 4 -> 3 -> 5
print(Solution().reverseKGroup(build([1, 2, 3, 4, 5]), 3).show_chain())
# 3 -> 2 -> 1 -> 4 -> 5

class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # 计算链表长度 n = 0 cur = head while cur: n += 1 cur = cur.next # 前置设置 dummy = ListNode(next=head) p0 = dummy cur = head # 循环反转 while n >= k: n -= k pre = None for _ in range(k): nxt = cur.next cur.next = pre pre = cur cur = nxt trail = p0.next # 组头 → 反转后变组尾 trail.next = cur # 连向下一组 p0.next = pre # 上一段连向新组头 p0 = trail # 推进组前驱 return dummy.next print(Solution().reverseKGroup(build([1, 2, 3, 4, 5]), 2).show_chain()) # 2 -> 1 -> 4 -> 3 -> 5 print(Solution().reverseKGroup(build([1, 2, 3, 4, 5]), 3).show_chain()) # 3 -> 2 -> 1 -> 4 -> 5

2 -> 1 -> 4 -> 3 -> 5 -> None
3 -> 2 -> 1 -> 4 -> 5 -> None

第 3 章 · 快慢指针模块¶

统一变量命名：slow / fast。 核心模板：

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

这一章覆盖：

• 找中点：876/234/148 的子步骤
• 判环：141
• 找环入口：142
• 间距为 N 的双指针：19（虽然速度相同，但起点不同，本质同源）

3.1 找中点 · 快慢指针子模板¶

奇偶差异要记清：

• 奇数（长度 5）：slow 落在正中心（第 3 个）
• 偶数（长度 4）：slow 落在下中点（第 3 个），即两个中点中靠后的那个

这一落点对 234 回文正好合适：反转后的段长度 ≤ 前半段，比较时以反转段结束为准。

In [8]:

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow


print(Solution().middleNode(build([1, 2, 3, 4, 5])).val)  # 3
print(Solution().middleNode(build([1, 2, 3, 4])).val)     # 3 (下中点)

class Solution: def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow print(Solution().middleNode(build([1, 2, 3, 4, 5])).val) # 3 print(Solution().middleNode(build([1, 2, 3, 4])).val) # 3 (下中点)

3
3

3.2 判环 · 141 环形链表¶

判断链表是否有环。

思路：快慢指针，有环必相遇，无环则 fast 先到 None。

In [9]:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

class Solution: def hasCycle(self, head: Optional[ListNode]) -> bool: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False

3.3 找环入口 · 142 环形链表 II¶

返回环的入口节点，无环返回 None。

推导：设表头到入口长 a，环长 b。第一次相遇时 slow 走了 s，fast 走了 2s，且 2s - s = nb → s = nb。也就是说 slow 从相遇点再走 a 步就到入口，而 a 步正好等于从表头出发走 a 步。

做法：相遇后把 fast 拉回表头，两指针同速走，再次相遇即入口。

In [10]:

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                fast = head
                while fast is not slow:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None

class Solution: def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]: slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: fast = head while fast is not slow: fast = fast.next slow = slow.next return slow return None

3.4 间距为 N 的双指针 · 19 删除倒数第 N 个¶

与快慢指针的区别：这里两指针速度相同，但起点相差 N。当右指针到尾时，左指针恰好在倒数第 N+1 个位置（即被删节点的前驱）。

dummy 的作用：待删节点可能是头节点，此时需要前驱。dummy 让头节点也有前驱可用。

变量约定：left / right（起点相同，right 先走 n+1 步，保证 left 最终落在前驱位置）。

In [11]:

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        left = right = dummy

        for _ in range(n):      # right 先走 n 步（间距 = n）
            right = right.next

        while right.next:       # right 到尾时，left 到被删节点的前驱
            left = left.next
            right = right.next

        left.next = left.next.next
        return dummy.next


print(Solution().removeNthFromEnd(build([1, 2, 3, 4, 5]), 2).show_chain())  # 1->2->3->5
print(Solution().removeNthFromEnd(build([1]), 1))                          # None

class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(next=head) left = right = dummy for _ in range(n): # right 先走 n 步（间距 = n） right = right.next while right.next: # right 到尾时，left 到被删节点的前驱 left = left.next right = right.next left.next = left.next.next return dummy.next print(Solution().removeNthFromEnd(build([1, 2, 3, 4, 5]), 2).show_chain()) # 1->2->3->5 print(Solution().removeNthFromEnd(build([1]), 1)) # None

1 -> 2 -> 3 -> 5 -> None
None

第 4 章 · 等距拼接模块¶

4.1 路径等长切换 · 160 相交链表¶

返回两链表的相交节点。

统一变量命名：pA / pB。 核心原理：两指针分别遍历 A 和 B，走到末尾就切到另一条，总路径都是 len(A) + len(B)。如果相交，两指针会在相交点相遇；不相交则同时到 None。

In [12]:

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        pA, pB = headA, headB
        while pA is not pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: if not headA or not headB: return None pA, pB = headA, headB while pA is not pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

第 5 章 · 哑节点构建新链表模块¶

这一章是 dummy 最经典的落地场景。当你需要边遍历边构建一条全新的链表、而新链表的头在执行前不确定时，就用这个模板：

dummy = ListNode()
cur = dummy
while ...:
    cur.next = some_new_node
    cur = cur.next
return dummy.next

统一变量命名：dummy / cur / l1 / l2。

包含题目：

• 21 合并两个有序链表（最经典）
• 2 两数相加
• 86 分隔链表（双 dummy）
• 82 删除排序链表重复元素 II（dummy + 前驱判断）

5.1 拉链合并 · 21 合并两个有序链表¶

经典得不能再经典的 dummy 用法。两条升序链表合并成一条升序链表。

In [13]:

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next


print(Solution().mergeTwoLists(build([1, 2, 4]), build([1, 3, 4])).show_chain())
# 1 -> 1 -> 2 -> 3 -> 4 -> 4

class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1 l1 = l1.next else: cur.next = l2 l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next print(Solution().mergeTwoLists(build([1, 2, 4]), build([1, 3, 4])).show_chain()) # 1 -> 1 -> 2 -> 3 -> 4 -> 4

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None

5.2 进位模拟 · 2 两数相加¶

两个逆序存放的非负整数链表相加，返回同样逆序的结果链表。

核心：三个来源可能还有值 —— l1、l2、carry。只要任一存在就继续循环。

In [14]:

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry % 10)
            carry //= 10
            cur = cur.next
        return dummy.next


# 342 + 465 = 807
r = Solution().addTwoNumbers(build([2, 4, 3]), build([5, 6, 4]))
print(r.show_chain())   # 7 -> 0 -> 8

class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy carry = 0 while l1 or l2 or carry: if l1: carry += l1.val l1 = l1.next if l2: carry += l2.val l2 = l2.next cur.next = ListNode(carry % 10) carry //= 10 cur = cur.next return dummy.next # 342 + 465 = 807 r = Solution().addTwoNumbers(build([2, 4, 3]), build([5, 6, 4])) print(r.show_chain()) # 7 -> 0 -> 8

7 -> 0 -> 8 -> None

5.3 链表分隔 · 86 分隔链表¶

把所有小于 x 的节点排在大于等于 x 的节点之前，保持两部分内各自的相对顺序。

思路：用两个 dummy 分别构建"小链表"和"大链表"，最后拼接。这是 dummy"构建入口"能力的直接延伸——需要构建几条链表就备几个 dummy。

In [15]:

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        small_dummy, big_dummy = ListNode(), ListNode()
        small_cur, big_cur = small_dummy, big_dummy

        cur = head
        while cur:
            if cur.val < x:
                small_cur.next = cur
                small_cur = small_cur.next
            else:
                big_cur.next = cur
                big_cur = big_cur.next
            cur = cur.next

        big_cur.next = None              # 必须截断，否则可能成环
        small_cur.next = big_dummy.next
        return small_dummy.next


print(Solution().partition(build([1, 4, 3, 2, 5, 2]), 3).show_chain())
# 1 -> 2 -> 2 -> 4 -> 3 -> 5

class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: small_dummy, big_dummy = ListNode(), ListNode() small_cur, big_cur = small_dummy, big_dummy cur = head while cur: if cur.val < x: small_cur.next = cur small_cur = small_cur.next else: big_cur.next = cur big_cur = big_cur.next cur = cur.next big_cur.next = None # 必须截断，否则可能成环 small_cur.next = big_dummy.next return small_dummy.next print(Solution().partition(build([1, 4, 3, 2, 5, 2]), 3).show_chain()) # 1 -> 2 -> 2 -> 4 -> 3 -> 5

1 -> 2 -> 2 -> 4 -> 3 -> 5 -> None

5.4 删除排序链表重复元素 II · 82¶

升序链表中，删除所有出现重复的节点（重复的一个不留）。

思路：dummy + 前驱指针 cur。如果发现 cur.next.val == cur.next.next.val，就把所有等于该值的节点一次性跳过。

dummy 的必要性：头节点本身可能重复（如 [1,1,2]），必须有前驱。

In [ ]:

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        p0 = dummy   # 已确认保留区的最后一个节点
        cur = head     # 正在审查的节点
        
        while cur and cur.next:
            if cur.val == cur.next.val:    # 判断 cur 是否是一段重复的起点
                dup_val = cur.val
                while cur and cur.val == dup_val:   # cur 一路跳过所有值等于 dup_val 的节点
                    cur = cur.next
                p0.next = cur           # 把保留区的尾巴接到 cur 上，等于一刀切掉中间那段
            else:                       # cur 是唯一值，保留它，prev 跟着前进
                p0 = cur
                cur = cur.next
        return dummy.next
print(Solution().deleteDuplicates(build([1, 2, 3, 3, 4, 4, 5])).show_chain())
# 1 -> 2 -> 5
print(Solution().deleteDuplicates(build([1, 1, 1, 2, 3])).show_chain())
# 2 -> 3

class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(next=head) p0 = dummy # 已确认保留区的最后一个节点 cur = head # 正在审查的节点 while cur and cur.next: if cur.val == cur.next.val: # 判断 cur 是否是一段重复的起点 dup_val = cur.val while cur and cur.val == dup_val: # cur 一路跳过所有值等于 dup_val 的节点 cur = cur.next p0.next = cur # 把保留区的尾巴接到 cur 上，等于一刀切掉中间那段 else: # cur 是唯一值，保留它，prev 跟着前进 p0 = cur cur = cur.next return dummy.next print(Solution().deleteDuplicates(build([1, 2, 3, 3, 4, 4, 5])).show_chain()) # 1 -> 2 -> 5 print(Solution().deleteDuplicates(build([1, 1, 1, 2, 3])).show_chain()) # 2 -> 3

1 -> 2 -> 5 -> None
2 -> 3 -> None

第 6 章 · 分治模块（反转 + 快慢 + Dummy 的综合）¶

分治 = 把一个大链表问题拆成两个规模减半的小问题，递归解决，再合并。 合并这一步通常复用 5.1 拉链合并。

这一章把前面几章的基础模块串起来：

• 148 排序链表 = 3.1 找中点 + 递归 + 5.1 合并
• 23 合并 K 链表 = 反复调用 5.1
• 143 重排链表 = 3.1 找中点 + 2.1 反转 + 5.1 合并（三大模块的终极组合）

6.1 链表归并排序 · 148 排序链表¶

O(n log n) 时间、O(1) 空间（忽略递归栈）排序链表。

三步：

1. 找中点（3.1），并从中点切断
2. 递归排序左右半段
3. 合并两个有序链表（5.1）

In [18]:

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

        # 1. 找中点：注意这里让 fast 从 head.next 出发，保证偶数长度 slow 落在"上中点"，便于切断
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None

        # 2. 递归
        left_half = self.sortList(head)
        right_half = self.sortList(mid)

        # 3. 合并（复用 5.1）
        return self._merge(left_half, right_half)

    def _merge(self, l1, l2):
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1; l1 = l1.next
            else:
                cur.next = l2; l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next


print(Solution().sortList(build([4, 2, 1, 3])).show_chain())
# 1 -> 2 -> 3 -> 4

class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head or not head.next: return head # 1. 找中点：注意这里让 fast 从 head.next 出发，保证偶数长度 slow 落在"上中点"，便于切断 slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None # 2. 递归 left_half = self.sortList(head) right_half = self.sortList(mid) # 3. 合并（复用 5.1） return self._merge(left_half, right_half) def _merge(self, l1, l2): dummy = ListNode() cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1; l1 = l1.next else: cur.next = l2; l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next print(Solution().sortList(build([4, 2, 1, 3])).show_chain()) # 1 -> 2 -> 3 -> 4

1 -> 2 -> 3 -> 4 -> None

6.2 K 路两两合并 · 23 合并 K 个升序链表¶

把 k 条升序链表合并成一条。

思路：每一轮把相邻两条合并，k 条变 k/2 条，循环 log k 轮。总复杂度 O(N log k)，N 为节点总数。

注意：不要用顺序合并（每次把下一条合进"大链表"），那样是 O(Nk)。分治两两合并才是 O(N log k)。

In [ ]:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 额外提前判断
        lists = [h for h in lists if h]
        if not lists:
            return None
        
        while len(lists) > 1:
            nxt_round = []
            # 将lists中的链表数，两两合并，nxt_round中的数量每完整经过一次合并就变为远来的一半，直到len(lists)=1的时候，退出循环
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                nxt_round.append(self._merge(l1, l2))
            lists = nxt_round   # 将一次合并循环后的结果重新复制给lists
        return lists[0]

    def _merge(self, l1, l2):
        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1; l1 = l1.next
            else:
                cur.next = l2; l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next


r = Solution().mergeKLists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])
print(r.show_chain())   # 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: # 额外提前判断 lists = [h for h in lists if h] if not lists: return None while len(lists) > 1: nxt_round = [] # 将lists中的链表数，两两合并，nxt_round中的数量每完整经过一次合并就变为远来的一半，直到len(lists)=1的时候，退出循环 for i in range(0, len(lists), 2): l1 = lists[i] l2 = lists[i + 1] if i + 1 < len(lists) else None nxt_round.append(self._merge(l1, l2)) lists = nxt_round # 将一次合并循环后的结果重新复制给lists return lists[0] def _merge(self, l1, l2): dummy = ListNode() cur = dummy while l1 and l2: if l1.val <= l2.val: cur.next = l1; l1 = l1.next else: cur.next = l2; l2 = l2.next cur = cur.next cur.next = l1 if l1 else l2 return dummy.next r = Solution().mergeKLists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])]) print(r.show_chain()) # 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> None

6.3 重排链表 · 143 ⭐ 三大模块终极组合¶

把 L0 → L1 → ... → Ln-1 → Ln 重排成 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...。

这道题是整个链表专题的毕业考：

1. 找中点（3.1）把链表切成两半
2. 反转后半段（2.1）
3. 交替拼接（类似 5.1，但不是按值大小而是交替）

做完这道题，反转 / 快慢 / Dummy 三大模块就算打通了。

In [20]:

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

        # 1. 找中点
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半段（以 slow 为分界点，反转 slow.next 开始的段更干净）
        pre, cur = None, slow.next
        slow.next = None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        head2 = pre

        # 3. 交替拼接
        l1, l2 = head, head2
        while l2:
            nxt1, nxt2 = l1.next, l2.next
            l1.next = l2
            l2.next = nxt1
            l1, l2 = nxt1, nxt2


head = build([1, 2, 3, 4, 5])
Solution().reorderList(head)
print(head.show_chain())   # 1 -> 5 -> 2 -> 4 -> 3

class Solution: def reorderList(self, head: Optional[ListNode]) -> None: if not head or not head.next: return # 1. 找中点 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 2. 反转后半段（以 slow 为分界点，反转 slow.next 开始的段更干净） pre, cur = None, slow.next slow.next = None while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt head2 = pre # 3. 交替拼接 l1, l2 = head, head2 while l2: nxt1, nxt2 = l1.next, l2.next l1.next = l2 l2.next = nxt1 l1, l2 = nxt1, nxt2 head = build([1, 2, 3, 4, 5]) Solution().reorderList(head) print(head.show_chain()) # 1 -> 5 -> 2 -> 4 -> 3

1 -> 5 -> 2 -> 4 -> 3 -> None

第 7 章 · 结构映射模块¶

当链表节点之间的引用关系不再是简单的 next 链（比如多了 random 指针、或需要高频增删改的双向结构），就需要用哈希表或辅助数据结构来追踪节点间的映射关系。

包含：

• 138 随机链表复制（哈希映射 / 节点交织两种解法）
• 146 LRU 缓存（哈希 + 双向链表）

7.1 随机链表复制 · 138¶

链表每个节点除 next 外还有 random 指针，指向链表中任意节点或 null。要求深拷贝。

为什么不能一次遍历搞定：random 可能指向还没被创建的后续节点。普通链表的 next 总是指向下一个（遍历顺序后继），所以单次遍历能完成——但 random 破坏了这个性质。

两种解法：

1. 哈希映射（空间 O(n)，代码最清晰）

   • 第一遍：为每个老节点建对应新节点，存 old → new 映射
   • 第二遍：用映射补全每个新节点的 next / random

2. 节点交织（空间 O(1)，巧妙）

   • 把每个新节点插入到对应老节点后面：A → A' → B → B' → C → C'
   • 这样 old_X.next 就是 new_X，new_X.random 直接等于 old_X.random.next
   • 最后拆分两条链表即可

In [21]:

class Node:
    def __init__(self, x: int, next=None, random=None):
        self.val = x
        self.next = next
        self.random = random


# 解法 1：哈希映射
class SolutionHash:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None
        old_to_new = {}
        cur = head
        while cur:
            old_to_new[cur] = Node(cur.val)
            cur = cur.next
        cur = head
        while cur:
            if cur.next:
                old_to_new[cur].next = old_to_new[cur.next]
            if cur.random:
                old_to_new[cur].random = old_to_new[cur.random]
            cur = cur.next
        return old_to_new[head]


# 解法 2：节点交织（O(1) 空间）
class SolutionWeave:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None
        # 1. 交织：每个老节点后插一个副本
        cur = head
        while cur:
            copy = Node(cur.val, next=cur.next)
            cur.next = copy
            cur = copy.next
        # 2. 设置副本的 random
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # 3. 拆分
        new_head = head.next
        cur_old, cur_new = head, new_head
        while cur_old:
            cur_old.next = cur_new.next
            cur_old = cur_old.next
            if cur_old:
                cur_new.next = cur_old.next
                cur_new = cur_new.next
        return new_head

class Node: def __init__(self, x: int, next=None, random=None): self.val = x self.next = next self.random = random # 解法 1：哈希映射 class SolutionHash: def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: if not head: return None old_to_new = {} cur = head while cur: old_to_new[cur] = Node(cur.val) cur = cur.next cur = head while cur: if cur.next: old_to_new[cur].next = old_to_new[cur.next] if cur.random: old_to_new[cur].random = old_to_new[cur.random] cur = cur.next return old_to_new[head] # 解法 2：节点交织（O(1) 空间） class SolutionWeave: def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: if not head: return None # 1. 交织：每个老节点后插一个副本 cur = head while cur: copy = Node(cur.val, next=cur.next) cur.next = copy cur = copy.next # 2. 设置副本的 random cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 3. 拆分 new_head = head.next cur_old, cur_new = head, new_head while cur_old: cur_old.next = cur_new.next cur_old = cur_old.next if cur_old: cur_new.next = cur_old.next cur_new = cur_new.next return new_head

7.2 LRU 缓存 · 146¶

设计 O(1) 的 get 和 put。容量满时淘汰最久未使用的键。

为什么哈希和双向链表必须一起用：

• 单哈希表：查找 O(1)，但没法维护"使用顺序"
• 单链表：顺序清晰，但查找和删除任一节点都要 O(n)
• 结合：哈希表 key → 节点，直接 O(1) 定位节点；双向链表维护顺序，任一节点都能 O(1) 自删除 / 移到尾部

设计：

• 双向链表两端加哨兵 head（最久未用端）和 tail（最近使用端），省去空链表判断
• get(key)：哈希表找到节点 → 摘除 → 移到 tail 端
• put(key, val)：存在则更新+移到 tail；不存在则新建插入 tail，超容量则淘汰 head 后的节点

In [22]:

class DLNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                     # key → DLNode
        self.head = DLNode()              # 哨兵：最久未用端
        self.tail = DLNode()              # 哨兵：最近使用端
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_to_tail(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._push_to_tail(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._push_to_tail(node)
            return
        node = DLNode(key, value)
        self.map[key] = node
        self._push_to_tail(node)
        if len(self.map) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.map[lru.key]


# 演示
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))   # 1
cache.put(3, 3)       # 淘汰 key=2
print(cache.get(2))   # -1
cache.put(4, 4)       # 淘汰 key=1
print(cache.get(1))   # -1
print(cache.get(3))   # 3
print(cache.get(4))   # 4

class DLNode: def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cap = capacity self.map = {} # key → DLNode self.head = DLNode() # 哨兵：最久未用端 self.tail = DLNode() # 哨兵：最近使用端 self.head.next = self.tail self.tail.prev = self.head def _remove(self, node): node.prev.next = node.next node.next.prev = node.prev def _push_to_tail(self, node): node.prev = self.tail.prev node.next = self.tail self.tail.prev.next = node self.tail.prev = node def get(self, key: int) -> int: if key not in self.map: return -1 node = self.map[key] self._remove(node) self._push_to_tail(node) return node.val def put(self, key: int, value: int) -> None: if key in self.map: node = self.map[key] node.val = value self._remove(node) self._push_to_tail(node) return node = DLNode(key, value) self.map[key] = node self._push_to_tail(node) if len(self.map) > self.cap: lru = self.head.next self._remove(lru) del self.map[lru.key] # 演示 cache = LRUCache(2) cache.put(1, 1) cache.put(2, 2) print(cache.get(1)) # 1 cache.put(3, 3) # 淘汰 key=2 print(cache.get(2)) # -1 cache.put(4, 4) # 淘汰 key=1 print(cache.get(1)) # -1 print(cache.get(3)) # 3 print(cache.get(4)) # 4

1
-1
-1
3
4

附录 · 技术模块 × 题目对照表¶

遮住代码只看这张表，应该能复述每道题的解法骨架。

题号	题目	反转	快慢	等距	Dummy	分治	映射
160	相交链表			✓
206	反转链表	✓
234	回文链表	✓	✓
92	反转链表 II	✓			✓
24	两两交换	✓			✓
25	K 个一组反转	✓			✓
141	环形链表		✓
142	环形链表 II		✓
19	倒数第 N 个		✓		✓
21	合并两有序				✓
2	两数相加				✓
86	分隔链表				✓
82	删除重复元素 II				✓
148	排序链表		✓		✓	✓
23	合并 K 个升序				✓	✓
143	重排链表 ⭐	✓	✓		✓
138	随机链表复制						✓
146	LRU 缓存						✓

---

统一命名速查¶

模块	变量名
反转三指针	pre / cur / nxt
快慢指针	slow / fast
间距双指针	left / right（起点相同，right 先走 N 步）
两链表等距切换	pA / pB
Dummy 构建	dummy / cur / l1 / l2
组反转	p0（组前驱）/ pre / cur / nxt（组内）/ trail（组头→组尾）
分治	mid / left_half / right_half
深拷贝	old_to_new（哈希映射）/ cur
LRU	head / tail（哨兵）/ prev / next