LeetCode（三）：链表操作

链表是最能逼你用指针思维思考的数据结构。数组支持 $$O(1)$$ 索引，底层内存布局不用你管。链表只丢给你一个 head 指针，然后问：“接下来怎么办？” 从索引到引用的这一步跨越，正是链表题频繁出现在面试里的原因。题目描述短，边界条件多，写对很难。它考察的正是优秀工程师的习惯：画图、给指针起名、解引用前必查 None。

本文挑了 5 道题。吃透它们，面试里的链表套路就全齐了：

Reverse a linked list — 指针重定向的基本功，迭代与递归双解。
Merge two sorted lists — dummy node 套路，专治头节点边界条件。
Linked list cycle detection (Floyd) — fast/slow pointers，以及证明它们会在入口相遇的代数推导。
Remove the nth node from end — 固定间距双指针，一次遍历搞定。
LRU cache — doubly linked list + hash map 组合，工业级缓存的标配。

每节结构固定：题目、思路、代码、复杂度、图解。配图展示了指针重定向前后的状态。脑子里过题、白板上写题，就该这么画。

系列导航#

LeetCode Patterns (10 篇): Hash Tables, Two Pointers, Linked List Operations (本文), Binary Tree Traversal, Dynamic Programming, Backtracking, Binary Search, Stacks and Queues, Graphs, Greedy and Bit Manipulation.

链表基础#

单链表节点只带一个值和一个指针：

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

接口就这么多。本文所有算法，本质都是按正确顺序执行 node.next = something，并加上必要的安全检查。

链表 vs 数组#

特性	Array	Linked list
随机访问	$$O(1)$$	$$O(n)$$
已知位置插入/删除	$$O(n)$$ (需移位)	$$O(1)$$ (改指针)
内存布局	Contiguous	Scattered
Cache locality	High	Low
动态扩容	需重新分配	天然支持

取舍很明确：数组胜在访问速度和 cache 命中率；链表胜在频繁修改，且不需要随机跳跃。明白这点，选题思路就清晰了。“需要直接跳到第 k 个元素？” 用 array。“需要原地切断中间节点，不拷贝数据？” 用 linked list。

插入与删除：重定向两个指针，多一个都不行#

把 X 插到 A 和 B 之间，严格只需两步赋值，顺序不能错：

1
2
X.next = A.next   # X 指向 B
A.next = X        # A 指向 X

顺序一反，A.next 被覆盖，B 直接丢失。删除更简单，一步赋值让 A 跳过 B，剩下的交给 garbage collector：

1
A.next = B.next   # A 跳过 B

核心就一句话：链表操作就是按特定顺序执行的指针赋值。本文剩下的内容，全是这个主题的变体。

LeetCode 206 — 反转链表#

给定单链表 head，反转链表并返回新 head。
示例: 1 → 2 → 3 → 4 → 5 变为 5 → 4 → 3 → 2 → 1。
进阶: 迭代与递归双解。

这是指针操作的 “hello world”。难点在于原地翻转所有 next 指针，同时不能断开后续节点的访问路径。

迭代法：三个指针， $$O(1)$$ 空间#

关键点：执行 curr.next = prev 会直接切断前进路线。必须先保存下一步。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def reverseList(head):
    """
    原地反转单链表。

    Time:  O(n) — 每个节点访问一次。
    Space: O(1) — 仅三个指针，无额外结构。
    """
    prev, curr = None, head
    while curr:
        nxt = curr.next     # 1. 保存前进路径
        curr.next = prev    # 2. 翻转当前指针
        prev = curr         # 3. prev 前移
        curr = nxt          # 4. curr 前移
    return prev             # prev 成为新 head (原 tail)

在 1 → 2 → 3 → None 上的执行过程：

步骤	`prev`	`curr`	翻转后状态
0	`None`	`1`	—
1	`1`	`2`	`None ← 1`, 剩余 `2 → 3 → None`
2	`2`	`3`	`None ← 1 ← 2`, 剩余 `3 → None`
3	`3`	`None`	`None ← 1 ← 2 ← 3`

返回 prev = 3，即反转后的 head。

循环已天然处理的边界条件：

空链表 (head is None)：循环不执行，直接返回 prev = None。
单节点：执行一次，1.next = None，返回 1。

递归法：回溯时重连#

递归视角：“反转 head 之后的所有节点，然后让原 head.next 指回 head。”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def reverseList_recursive(head):
    """
    递归反转链表。

    Time:  O(n).
    Space: O(n) — 递归调用栈。
    """
    if not head or not head.next:
        return head

    new_head = reverseList_recursive(head.next)

    # head.next 是已反转子链表的 tail。
    # 让 tail 指回 head，然后切断 head 的原向指针。
    head.next.next = head
    head.next = None
    return new_head

最容易卡壳的是 head.next.next = head。拆开看：

head.next 是原链表中紧跟 head 的节点。
递归返回后，该节点已成为反转子链表的 tail。
需要让 tail 指回 head，所以赋值给 head.next.next。

接着 head.next = None 切断原向连接，新 tail 正确终止。

迭代还是递归？#

写法	Time	Space	适用场景
Iterative	$$O(n)$$	$$O(1)$$	生产环境、长链表、避免 stack overflow
Recursive	$$O(n)$$	$$O(n)$$	白板演示、展示递归思维

面试先写迭代。补充递归展示思维广度。生产环境永远选迭代。Python 默认递归深度 1000，长链表直接爆栈。

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

拼接两个有序链表，返回一个新的有序链表。
示例: l1 = [1,2,4], l2 = [1,3,4] → [1,1,2,3,4,4]。

这题的难点不在合并逻辑，而在结果链表的第一个节点怎么处理。不用辅助节点，就得写特殊分支判断 head 来自 l1 还是 l2。引入 dummy node，分支直接消失。

迭代法：引入 dummy node#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def mergeTwoLists(l1, l2):
    """
    拼接节点合并两个有序链表 (不分配新节点)。

    Time:  O(m + n) — 每个输入节点访问一次。
    Space: O(1) — 仅 dummy node 和一个游标。
    """
    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

为什么用 dummy？ 它保证永远有一个“前驱节点”可以写入。不用 dummy，第一次循环就得决定 head 归属，后续所有分支都要跟着分叉。用了 dummy，每次循环逻辑完全一致。头节点边界被哨兵直接吸收。

在 l1 = [1,2,4], l2 = [1,3,4] 上的执行过程：

步骤	比较	选取	当前结果
1	`1 ≤ 1`	`l1`	`1`
2	`1 < 2`	`l2`	`1 → 1`
3	`2 < 3`	`l1`	`1 → 1 → 2`
4	`3 < 4`	`l2`	`1 → 1 → 2 → 3`
5	`4 ≤ 4`	`l1`	`1 → 1 → 2 → 3 → 4`
6	`l1` 为空	接入 `l2` 剩余部分	`1 → 1 → 2 → 3 → 4 → 4`

返回 dummy.next。

递归写法#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def mergeTwoLists_recursive(l1, l2):
    """
    递归合并。代码简洁但占用 O(m + n) 栈空间。

    Time:  O(m + n).
    Space: O(m + n) — 递归深度等于总长度。
    """
    if not l1: return l2
    if not l2: return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists_recursive(l1, l2.next)
        return l2

LeetCode 141 / 142 — Linked List Cycle (及入口定位)#

141: 判断链表是否有环。
142: 返回环的入口节点，无环返回 None。
限制: $$O(1)$$ 额外空间。

暴力解法（hash 记录节点、或计步）能过，但占 $$O(n)$$ 空间或需两次遍历。Floyd’s tortoise-and-hare 算法用两个指针加一段代数推导，一次遍历搞定。

第一阶段：检测环#

1
2
3
4
5
6
7
8
9
def hasCycle(head):
    """LeetCode 141. 使用 fast/slow pointers 检测环。"""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next         # 走 1 步
        fast = fast.next.next    # 走 2 步
        if slow is fast:
            return True
    return False

原理很简单。无环时，fast 碰到 None 循环结束。有环时，两个指针最终都会困在环里。fast 每步比 slow 多走一个节点，间距每轮缩 1。最多 $$L$$ 轮必相遇 ( $$L$$ 为环长)。

第二阶段：找环入口#

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def detectCycle(head):
    """
    LeetCode 142. 返回环的入口节点。

    Time:  O(n). Space: O(1).
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # 第二阶段：重置 slow，两者每次各走 1 步。
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

代数推导（建议记一次）#

设 $$a$$ = head 到入口的距离， $$b$$ = 入口沿环到相遇点的距离， $$c$$ = 环剩余部分 (环长 $$L = b + c$$ )。

\text{slow walked: } a + b

\text{fast walked: } a + b + kL \quad \text{(for some integer } k \geq 1\text{)}

2(a + b) = a + b + kL \implies a = kL - b = (k-1)L + c

最后一行是核心结论。它说明：从 head 走 $$a$$ 步到达入口，从相遇点走 $$a$$ 步也到达入口（因为 $$(k-1)L$$ 只是绕环整圈）。所以把 slow 重置到 head，两个指针每次各走一步，必然在入口相遇。

LeetCode 19 — 删除链表的倒数第 N 个结点#

给定链表 head，删除倒数第 n 个节点并返回 head。尝试一次遍历完成。
示例: head = [1,2,3,4,5], n = 2 → [1,2,3,5]。

朴素解法走两遍：先算长度，再走到 length - n 位置。一次遍历解法用两个指针，保持固定间距 $$n + 1$$ 。配合 dummy node，删除头节点也不需要特殊分支。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def removeNthFromEnd(head, n):
    """
    一次遍历删除倒数第 n 个节点。

    Time:  O(L) L 为链表长度。
    Space: O(1).
    """
    dummy = ListNode(0, head)    # 统一处理删除 head 的情况
    slow = fast = dummy

    # fast 先走 n+1 步。这样 fast 到 None 时，
    # slow 正好停在待删除节点的前一个位置。
    for _ in range(n + 1):
        fast = fast.next

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

    slow.next = slow.next.next
    return dummy.next

为什么是 $$n+1$$ 而不是 $$n$$ ？ 需要 slow 停在目标节点的前驱，才能执行 slow.next 重定向。如果 fast 只走 $$n$$ 步，间距为 $$n$$ ，fast 到 None 时 slow 正好踩在目标节点上，没法删。Off-by-one 是这里最常见的 bug。

为什么用 dummy？ 考虑 head = [1, 2], n = 2 (删 head)。有 dummy 时：

fast 走 3 步，停在 None。
slow 还在 dummy。
dummy.next = dummy.next.next 直接让 dummy.next = 2。
返回 dummy.next = 2。结束。

不用 dummy，就得写 if n == length: return head.next。这意味着必须先算长度。又退化成两遍遍历。

LeetCode 146 — LRU 缓存#

设计数据结构，支持 $$O(1)$$ 均摊时间的 get(key) 和 put(key, value)。容量满时，淘汰 least recently used 的 key。

这题无处不在。OS page cache、CDN edge cache、浏览器缓存、ORM query cache 全用它。标准解法是一个精巧的组合：hash map 负责 $$O(1)$$ 查找，doubly linked list 负责 $$O(1)$$ 排序与淘汰。

为什么需要两种数据结构？#

单用 hash map 能 $$O(1)$$ 查找，但记录不了访问顺序。
单用 linked list 能记录顺序，但查找是 $$O(n)$$ 。
组合起来：map 里 $$O(1)$$ 找到节点，doubly linked list 里 $$O(1)$$ 摘下并插到头部。

链表维护“最近访问在头，最久未访问在尾”的顺序。两个 sentinel 节点 (head 和 tail) 直接消灭头部插入和尾部淘汰的所有边界判断。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    """
    hash map + 带 sentinel 的 doubly linked list 实现 O(1) get/put。

    不变式:
        head <-> 最近访问 <-> ... <-> 最久未访问 <-> tail
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                       # key -> Node
        self.head, self.tail = Node(), Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    # ----- 链表基础操作 -----

    def _remove(self, node: "Node") -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: "Node") -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    # ----- 公开 API -----

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_to_front(node)            # 标记为最近访问
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_to_front(node)
            return

        if len(self.map) >= self.cap:
            lru = self.tail.prev            # 最久未访问节点
            self._remove(lru)
            del self.map[lru.key]

        new_node = Node(key, value)
        self.map[key] = new_node
        self._add_to_front(new_node)

三个关键细节：

Sentinel 不是可选项。 它们让所有插入和删除变成统一的四步指针操作。代码里看不到任何 if head is None。
节点必须存 key： 淘汰 LRU 节点时，需要从 map 里删掉对应的 key。节点不存 key，就得遍历 map 反查，复杂度直接退化。
get 只移动节点，不重新分配内存。 这才是均摊 $$O(1)$$ 的真正来源。

套路速查表#

技巧	适用场景	本文示例
Three pointers (`prev`, `curr`, `next`)	原地反转或重定向指针	Reverse Linked List
Dummy / sentinel node	head 可能被修改或替换	Merge Two Sorted Lists, Remove Nth From End, LRU
Fast / slow pointers	找中点、检测环、倒数第 k 个	Cycle II, Remove Nth From End
Hash map + linked list	需要 $$O(1)$$ 查找且维护顺序	LRU Cache
Recursion	操作天然具备分治结构	Recursive reverse / merge

常见坑点#

不判空直接解引用： curr.next.val 在 curr.next 为 None 时直接 crash。防御写法：while curr and curr.next:。
丢失前进路径： 写 curr.next = something 前，如果后续还要用原指针，必须先保存。迭代反转里的 nxt 变量就是干这个的。
忘记推进指针： 循环体内至少有一个指针向终止条件移动。否则死循环。
间距 off-by-one。 双指针间距题，fast 先走 n 还是 n + 1 直接决定对错。
不用 dummy node。 只要 head 可能变，上 dummy。5 行边界判断直接归零。

练习题#

按组内难度大致排序。

基础

LeetCode 206 — Reverse Linked List (已覆盖)
LeetCode 21 — Merge Two Sorted Lists (已覆盖)
LeetCode 19 — Remove Nth Node From End (已覆盖)
LeetCode 234 — Palindrome Linked List

环与相交

LeetCode 141 — Linked List Cycle (已覆盖)
LeetCode 142 — Linked List Cycle II (已覆盖)
LeetCode 160 — Intersection of Two Linked Lists

进阶

LeetCode 25 — Reverse Nodes in k-Group
LeetCode 23 — Merge K Sorted Lists
LeetCode 138 — Copy List with Random Pointer
LeetCode 146 — LRU Cache (已覆盖)
LeetCode 460 — LFU Cache

参考文献#

Introduction to Algorithms — Chapter 10, Elementary Data Structures.
Cracking the Coding Interview — 第 2 章 , Linked Lists.
VisuAlgo — Linked List visualization: https://visualgo.net/en/list
LeetCode Linked List tag — 100+ curated problems for practice.

链表在工业界的真实身影#

业务代码很少直接碰 ListNode。语言标准库把它藏起来了。但底层全是它的身影：

LRU caches。 functools.lru_cache、Redis 的 allkeys-lru 淘汰策略、浏览器 HTTP cache。底层全是 hash map + doubly linked list，和 LeetCode 146 一模一样。面试考这题，真正想问的是：为什么 Python list 做不到 $$O(1)$$ move-to-front？因为缺节点指针。
Linux kernel lists。 include/linux/list.h 定义了侵入式 doubly linked list。进程链表、文件描述符表、网络队列全用它。让侵入式链表跑起来的 container_of 宏，是内核 C 代码里最优雅的设计之一。
Java LinkedHashMap 与 Python OrderedDict。 按插入顺序迭代，底层就是 hash map 加 entry linked list。结构相同，语言不同。
Redis sorted sets 里的 Skip lists。 多层 linked list 加概率捷径。选它是因为比平衡树更容易实现 lock-free。

结论很直接：链表题不是“练习题”。它们是你在系统各层都会反复遇到的底层模式的最小切片。

更地道的 Python 写法#

LeetCode 默认风格是“披着 Python 皮的 C”。改几处，代码更好写也好读：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# 用 generator 遍历链表。
def to_list(head):
    while head:
        yield head.val
        head = head.next

# 按内容对比两个链表 (写测试极好用)。
assert list(to_list(result)) == [1, 2, 3, 4]

# 从 Python iterable 构建链表 (初始化数据极好用)。
def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

这三个辅助函数把“手动追踪指针”的测试变成一行代码。我每个链表文件开头都会贴上。

反转链表时，递归写法比迭代更短，且能直观体现结构。确认栈深度安全后可以直接用：

1
2
3
4
5
6
7
def reverse(head):
    if not head or not head.next:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

head.next.next = head 就是整个算法。读作：“我后面的节点，现在指回我。”

高频 Bug：遍历时直接修改指针#

双指针链表代码长得像数组代码，但出错后果完全不同。最常见的致命错误：

1
2
3
4
5
# 错误 — 修改 curr.next 前没保存下一个节点
curr = head
while curr:
    curr.next = something_new   # 链表后半段直接丢失
    curr = curr.next            # 现在顺着新指针走了

修复原则只有一条：任何触碰 .next 的赋值前，必须先保存原指针：

1
2
3
4
5
curr = head
while curr:
    nxt = curr.next             # 先保存
    curr.next = something_new
    curr = nxt                  # 再用保存的指针前进

所有迭代链表算法都遵守这个模式。代码跳节点、死循环、或“丢了一半链表”，十有八九是赋值跑在了保存前面。

链表代码自测清单#

提交前，脑子里过一遍：

测试用例	为什么重要
`head` 为 `None`	`while curr` 和 `while curr.next` 在这里行为不同
单节点	反转、合并、删除倒数第 N 个都有单节点退化情况
双节点	指针顺序起作用的最小场景
全相同值	能抓出错误的“跳过重复值”逻辑
长度为 1 的环 (节点自指)	Floyd 的 `slow == fast` 检查必须能触发
删除 head	dummy node 套路就是为这个存在的
删除 tail	`prev.next = None` 必须真正执行

每行 5 秒，总共半分钟。能省下大量调试时间。

总结#

链表题考的从来不是链表本身。考的是对状态变更的精确控制：给指针起名、排好赋值顺序、绝不假设 next 非空。上面 5 道题覆盖了所有核心技巧：指针重定向、dummy node、fast/slow traversal、固定间距双指针、hash map + list 组合。

能默写 reverseList，能在餐巾纸上讲清 Floyd 算法的推导，剩下的链表题就全是这些套路的排列组合。下一篇我们离开一维指针链，进入 binary trees。在那里，recursion 不再是炫技，而是最自然的解题工具。

LeetCode（三）：链表操作

系列导航#

链表基础#

链表 vs 数组#

插入与删除：重定向两个指针，多一个都不行#

LeetCode 206 — 反转链表#

迭代法：三个指针， $$O(1)$$ 空间#

递归法：回溯时重连#

迭代还是递归？#

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

迭代法：引入 dummy node#

递归写法#

LeetCode 141 / 142 — Linked List Cycle (及入口定位)#

第一阶段：检测环#

第二阶段：找环入口#

代数推导（建议记一次）#

LeetCode 19 — 删除链表的倒数第 N 个结点#

LeetCode 146 — LRU 缓存#

为什么需要两种数据结构？#

套路速查表#

常见坑点#

练习题#

参考文献#

链表在工业界的真实身影#

更地道的 Python 写法#

高频 Bug：遍历时直接修改指针#

链表代码自测清单#

总结#

LeetCode 算法模式 10 篇

读有所得？

系列导航#

链表基础#

链表 vs 数组#

插入与删除：重定向两个指针，多一个都不行#

LeetCode 206 — 反转链表#

迭代法：三个指针，$O(1)$ 空间#

递归法：回溯时重连#

迭代还是递归？#

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

迭代法：引入 dummy node#

递归写法#

LeetCode 141 / 142 — Linked List Cycle (及入口定位)#

第一阶段：检测环#

第二阶段：找环入口#

代数推导（建议记一次）#

LeetCode 19 — 删除链表的倒数第 N 个结点#

LeetCode 146 — LRU 缓存#

为什么需要两种数据结构？#

套路速查表#

常见坑点#

练习题#

参考文献#

链表在工业界的真实身影#

更地道的 Python 写法#

高频 Bug：遍历时直接修改指针#

链表代码自测清单#

总结#

LeetCode 算法模式 10 篇

读有所得？

迭代法：三个指针， $$O(1)$$ 空间#