本篇题目#

链表基础概念#

链表 vs 数组#

链表的每个节点在内存里是独立的对象，彼此通过 next 指针相连，不像数组那样连续存储。

1
数组：[1][2][3][4]  ← 内存连续，下标直接访问
2

3
链表：[1]→[2]→[3]→[4]→None  ← 靠指针串联，只能顺序访问

TIP
链表里所有变量都是指针（引用）
list1、list2、dummy、cur 这些变量存的都是节点的地址，不是节点本身。修改 cur.next 就是改那个节点里存的地址，不会复制节点。

虚拟头节点（dummy node）#

链表题几乎必用的技巧。创建一个值无意义的节点放在结果链表最前面，让所有节点都能用统一的方式处理，不需要对”第一个节点”做特殊判断。

1
dummy = ListNode(0)
2
cur = dummy
3
# ... 中间构建链表 ...
4
return dummy.next  # dummy 本身不算，从 dummy.next 开始才是真正的结果

链表通用模板#

模板① 构建 / 拼接链表#

适用：合并链表、删除节点、重排链表

1
dummy = ListNode(0)  # 虚拟头节点，值无意义，只是占个位
2
cur = dummy          # cur 是"建造指针"，始终指向结果链表的最后一个节点
3

4
while <根据题目决定终止条件>:
5
    cur.next = <某个节点或 ListNode(val)>  # 把新节点接到链表尾部
6
    cur = cur.next                         # cur 往后移，准备接下一个
7

8
# 注意：while 的终止条件每道题不同，不一定是 while head
9
# 例：合并两个链表 → while list1 and list2
10
# 例：合并K个（堆版）→ while h（堆不空）
11
# 例：遍历一条链表 → while head
12

13
return dummy.next  # dummy 是占位符，真正的结果从 dummy.next 开始
14
                   # 顺着 next 指针走就能访问整条链表

模板② 快慢指针#

适用：找中点、找倒数第 N 个、判断环

1
slow = head  # 慢指针，每次走一步
2
fast = head  # 快指针，每次走两步
3

4
while fast and fast.next:
5
    # fast and fast.next 两个条件都要判断：
6
    # fast        → 防止 fast 本身为 None 时报错
7
    # fast.next   → 防止 fast.next 为 None，下一步 fast.next.next 报错
8
    slow = slow.next       # 慢指针走一步
9
    fast = fast.next.next  # 快指针走两步
10

11
# 循环结束后：
12
# 奇数个节点 → slow 在正中间
13
# 偶数个节点 → slow 在中间偏右的那个

模板③ 反转链表#

适用：反转整条或部分链表

1
prev = None  # prev 指向已反转部分的头，初始为 None（反转后末尾接 None）
2
cur = head   # cur 是当前处理的节点
3

4
while cur:
5
    nxt = cur.next   # 先保存 cur 的下一个节点，否则反转后就找不到了
6
    cur.next = prev  # 把 cur 的 next 指向前一个节点，完成反转
7
    prev = cur       # prev 往前移到 cur
8
    cur = nxt        # cur 往前移到原来保存的下一个节点
9

10
# 循环结束时 cur 为 None，prev 指向原链表最后一个节点，即新链表的头
11
return prev

模板④ 双指针（记录前驱）#

适用：删除节点时需要记录前一个节点

1
dummy = ListNode(0)  # 虚拟头节点，防止删除的是 head 节点时没有前驱
2
dummy.next = head
3
prev = dummy  # prev 始终指向 cur 的前一个节点
4
cur = head    # cur 是当前检查的节点
5

6
while cur:
7
    if <满足删除条件>:
8
        prev.next = cur.next  # 跳过 cur，直接把 prev 连到 cur 的下一个
9
                              # prev 不动，因为下一个节点还没检查
10
    else:
11
        prev = cur            # 不删除，prev 跟着往前移
12
    cur = cur.next            # cur 每轮都往前移
13

14
return dummy.next

IMPORTANT
模板选择原则
本篇三道题都用模板①，区别只在中间逻辑：双指针比大小 / 排序后建链表 / 拆成两条链表再拼接。先把框架写出来，再想中间怎么填。

LeetCode 21 · 合并两个有序链表#

#21合并两个有序链表

Easy

思路#

双指针同时扫两条链表，每次把较小的节点接到结果链表后面，直到其中一条走完，把剩下的直接接上。

TIP
不需要创建新节点
直接把原节点重新串联，只改指针，不 new 节点。空间复杂度 O(1)。

代码#

1
class Solution:
2
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
3
        cur = dum = ListNode(0)
4
        while list1 and list2:
5
            if list1.val < list2.val:
6
                cur.next, list1 = list1, list1.next
7
            else:
8
                cur.next, list2 = list2, list2.next
9
            cur = cur.next
10
        cur.next = list1 if list1 else list2
11
        return dum.next

关键细节#

cur.next, list1 = list1, list1.next — Python 多重赋值，两侧同时求值，等价于：

1
cur.next = list1       # 把 list1 当前节点接到结果链表
2
list1 = list1.next     # list1 往后移一步

不需要手动断开旧连接：下一轮 cur.next = ... 写入新值时，旧的 cur.next 自然被覆盖，不需要额外操作。

cur.next = list1 if list1 else list2 — 循环结束时必有一条链表先走完，剩下那条直接整体接上，因为它本身已经有序。

总结#

核心技巧：模板① + 双指针，复用原节点
复杂度：时间 O(m+n)，空间 O(1)

LeetCode 23 · 合并K个升序链表#

#23合并K个升序链表

Hard

思路一：排序（暴力）#

把所有节点的值倒进数组，排序，再逐个建新节点。

1
class Solution:
2
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
3
        nums = []
4
        dummy = ListNode(0)
5
        curr = dummy
6

7
        for p in lists:        # p 拿到的是每条链表的头节点
8
            while p:
9
                nums.append(p.val)
10
                p = p.next
11

12
        nums.sort()            # 注意：不是 nums = nums.sort()，后者返回 None
13

14
        for i in nums:
15
            curr.next = ListNode(i)   # 每个整数都要包装成新节点
16
            curr = curr.next
17

18
        return dummy.next

TIP
为什么要 ListNode(i) 而不是直接用 i
nums 是普通 Python 列表，里面装的是整数。链表需要 ListNode 对象，所以必须把每个整数重新包装成节点。这和 21 题不同——那题直接复用原节点，这里是全新建节点。

TIP
常见 bug
nums = nums.sort() 会把 nums 赋值为 None，因为 .sort() 原地排序，返回值是 None。正确写法是 nums.sort()，直接修改原列表。

复杂度：时间 O(N log N)，空间 O(N)，N 为所有节点总数

思路二：最小堆（进阶）#

堆里始终只保留 K 个节点（每条链表的当前头），每次 pop 最小值、push 它的下一个节点，堆大小始终 ≤ K。

1
from heapq import heapify, heappop, heappush
2

3
ListNode.__lt__ = lambda a, b: a.val < b.val  # 让堆可以比较节点大小
4

5
class Solution:
6
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
7
        cur = dummy = ListNode()
8
        h = [head for head in lists if head]  # 把所有非空链表的头节点入堆
9
        heapify(h)                             # 原地堆化，O(K)
10
        while h:
11
            node = heappop(h)          # 取出当前最小节点
12
            if node.next:
13
                heappush(h, node.next) # 把它的下一个节点补充进堆
14
            cur.next = node            # 直接复用原节点，不建新节点
15
            cur = cur.next
16
        return dummy.next

IMPORTANT
ListNode.__lt__ = lambda a, b: a.val < b.val 的作用
堆需要比较元素大小，Python 对整数天然支持 <，但对 ListNode 对象不知道怎么比，会报错： TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
__lt__ 是 Python 的魔法方法（less than），给 ListNode 打补丁，告诉 Python 比节点就是比 val。因为 ListNode 是题目给的无法修改，所以用这种从外部打补丁的方式加上去。

TIP
heapq 三个核心函数

函数作用时间复杂度
heapify(h) 把普通列表原地变成最小堆 O(K)
heappush(h, val) 插入一个元素，自动维护堆结构 O(log K)
heappop(h) 取出并返回最小值，自动调整 O(log K)
Python 的堆是最小堆，h[0] 可以直接查看堆顶（最小值）。

函数	作用	时间复杂度
`heapify(h)`	把普通列表原地变成最小堆	O(K)
`heappush(h, val)`	插入一个元素，自动维护堆结构	O(log K)
`heappop(h)`	取出并返回最小值，自动调整	O(log K)

两种思路对比#

	排序暴力	最小堆
堆/数组大小	O(N)，全部节点	O(K)，K 条链表
时间复杂度	O(N log N)	O(N log K)
是否建新节点	是，`ListNode(i)`	否，复用原节点
适用场景	K 较大，N 较小	K 远小于 N 时更优

LeetCode 86 · 分隔链表#

#86分隔链表

Medium

思路#

同时维护两条链表：small 收集所有小于 x 的节点，big 收集大于等于 x 的节点，最后把两条拼起来。相当于模板①用了两次。

代码#

1
class Solution:
2
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
3
        small_curr = small_dummy = ListNode(0)
4
        big_curr = big_dummy = ListNode(0)
5

6
        while head:
7
            if head.val < x:
8
                small_curr.next = head
9
                small_curr = small_curr.next
10
            else:
11
                big_curr.next = head
12
                big_curr = big_curr.next
13
            head = head.next
14

15
        small_curr.next = big_dummy.next  # 把 big 链接到 small 尾部
16
        big_curr.next = None              # 切断 big 链末尾的旧指针
17

18
        return small_dummy.next

关键细节#

big_curr.next = None 为什么必须写？

节点是从原链表直接摘过来复用的，它们的 next 还保留着原来的指向。比如原链表是 1→4→3→2→5→2，节点 5 原来指着节点 2，如果不手动切断，结果链表末尾就会出现一个环，导致死循环。

1
不切断的错误情况：
2
... → 4 → 3 → 5 → 2 → （又回到了前面的节点）  ← 形成环！
3

4
切断后正确：
5
... → 4 → 3 → 5 → None  ✓

总结#

核心技巧：模板①用两次，拆分再合并
复杂度：时间 O(n)，空间 O(1)

三题横向对比#

题目	中间逻辑	是否建新节点	特殊处理
21 合并两个链表	双指针比大小	否，复用原节点	无
23 合并K个（排序版）	收集所有值排序	是，`ListNode(i)`	`nums.sort()` 别写成 `nums = nums.sort()`
23 合并K个（堆版）	最小堆动态取最小	否，复用原节点	需要给 `ListNode` 打补丁支持 `<` 比较
86 分隔链表	拆成两条再拼	否，复用原节点	末尾必须 `big_curr.next = None` 防止成环

IMPORTANT
链表题万能框架
1
dummy = ListNode(0)
2
cur = dummy
3
# ... 中间各种操作 ...
4
return dummy.next
不管中间逻辑怎么变，头尾这个框架几乎不变。先把框架写出来，再想中间填什么。