链表是最能逼着你用指针思考的数据结构。数组给你一个下标就能跳到任意位置；链表只丢给你一个头指针，剩下的全靠自己一步步走。这种从「随机访问」到「顺序追指针」的切换，正是链表题在面试里反复出现的原因——题目本身简单到一句话讲完，做对却要求你具备最基本的工程素养：画图、给指针起名字、绝不在没判空时解引用。

这篇文章用五道经典题目串起链表所有核心套路：

反转链表：指针重连的入门，迭代和递归两种写法都要会。
合并两个有序链表：理解「虚拟头节点」如何把第一个节点的特判消灭掉。
环形链表 II（Floyd 算法）：快慢指针 + 一段不长的代数推导，证明它们一定在入口相遇。
删除倒数第 N 个节点：固定间距的双指针，一次遍历搞定。
LRU 缓存：哈希表 + 双向链表的经典组合，几乎所有真实世界的缓存系统都用这个结构。

每一节的结构都一样：题目、思路、代码、复杂度、走一遍例子。下面那些图就是把指针在每一步是怎么动的画出来——这是你在白板上做这类题时大脑里应该跑的画面。

系列导航

LeetCode 算法精讲（共 10 篇）：哈希表、双指针、链表操作（本篇）、二叉树遍历、动态规划、回溯、二分查找、栈与队列、图算法、贪心与位运算。

链表基础

单链表节点很朴素，一个值加一个指针：

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

整个数据结构对外暴露的就这些。本文所有算法本质上都是「按正确顺序、配合正确的判空，做一连串 node.next = ... 赋值」。

链表 vs 数组

特性	数组	链表
随机访问	$O(1)$	$O(n)$
已知位置插入/删除	$O(n)$（需要搬移）	$O(1)$（只改指针）
内存布局	连续	分散
缓存友好	高	低
动态扩容	需要重新分配	天然支持

权衡很具体：数组在「访问 + 缓存命中率」上完胜，链表在「频繁中间插删 + 不需要随机跳转」时完胜。一旦想清楚这点，选数据结构就成了反射动作——“我要按下标取第 k 个？” 数组；“我要在中间剪一刀拼上不复制？” 链表。

插入与删除：永远只动两根指针

把 X 插到 A 和 B 之间，正好是两条赋值，顺序不能错：

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

如果反过来写，A.next 会先被覆盖，B 就再也找不到了。删除更简单，一行赋值让 A 跳过 B，剩下的事交给垃圾回收：

1
A.next = B.next

整个链表操作的心智模型就这么一句话：链表算法 = 按特定顺序执行的指针赋值序列。后面所有题目都是这个主题的变奏。

LeetCode 206：反转链表

给你单链表的头节点 head，反转链表后返回新的头节点。
示例：1 → 2 → 3 → 4 → 5 反转为 5 → 4 → 3 → 2 → 1。
进阶：迭代和递归两种方法都实现一遍。

这是指针操作的「Hello World」。难点在于：每一次翻转 next 都会立刻切断你前进的路，所以必须在翻转之前先存好「下一个去哪」。

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

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

    时间：O(n)，每个节点访问一次。
    空间：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 现在是新的头（原来的尾）

用 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 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):
    """
    递归反转。

    时间：O(n)。
    空间：O(n)，递归栈深度。
    """
    if not head or not head.next:
        return head

    new_head = reverseList_recursive(head.next)

    # head.next 是已反转子链表的尾节点
    # 让它指回 head，再断掉 head 的出边
    head.next.next = head
    head.next = None
    return new_head

让所有人都卡住的就是 head.next.next = head 这一行，一个字一个字读：

head.next 是原始链表里 head 的下一个节点。
递归调用结束后，这个节点已经成了反转子链表的尾节点。
我们想让这个尾节点指回 head，所以就给 head.next.next 赋值。

紧接着 head.next = None 切断 head 原来的出边，新尾巴干净地终止。

迭代还是递归？

写法	时间	空间	用在哪
迭代	$O(n)$	$O(1)$	生产代码、长链表，没有栈溢出风险
递归	$O(n)$	$O(n)$	白板上展示递归思维，秀代码简洁度

面试时先写迭代，再补一句「递归也能做」展示你思维不只一种。生产环境一律选迭代——Python 默认递归深度 1000，链表稍微长一点就崩。

LeetCode 21：合并两个有序链表

把两个有序链表拼成一个有序链表，节点直接复用，不要新建。
示例：l1 = [1,2,4]、l2 = [1,3,4] → [1,1,2,3,4,4]。

合并本身就是双指针比一比谁小，没什么花样。真正值得讲的是「结果链表的第一个节点怎么处理」——不用辅助节点的话，第一次循环必须特判「头节点从哪个链表来」，后面所有逻辑就跟着分叉。引入一个**虚拟头节点（dummy）**之后，这个特判直接消失。

迭代 + 虚拟头节点

 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):
    """
    通过拼接节点合并两个有序链表（不分配新节点）。

    时间：O(m + n)，每个输入节点访问一次。
    空间：O(1)，只用 dummy 和 cur 两个指针。
    """
    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？ 因为它保证了「永远有一个前驱节点可以写」。没有它的话，第一次迭代必须先决定头节点取自 l1 还是 l2，这个决定会让后面的代码到处分叉。有了 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) 栈。

    时间：O(m + n)。
    空间：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：环形链表与环入口

141：判断链表里有没有环。
142：返回环开始的那个节点；没环就返回 None。
要求：$O(1)$ 额外空间。

暴力法——把所有节点丢进哈希表、或者数步数——都对，但要么 $O(n)$ 空间，要么得遍历两次。Floyd 龟兔赛跑算法用一对指针、一段不长的代数，就能一次遍历搞定。

第一阶段：检测有没有环

1
2
3
4
5
6
7
8
9
def hasCycle(head):
    """LeetCode 141：快慢指针检测环。"""
    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 个节点，二者距离每次缩短 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：返回环的入口节点。

    时间：O(n)。空间：O(1)。
    """
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # 第二阶段：把 slow 拉回 head，两者各走 1 步
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

一次推导，终生受用

设 $a$ = 头节点到入口的距离，$b$ = 入口到相遇点（沿环方向）的距离，$c$ = 环上剩下的部分（所以环长 $L = b + c$）。

slow 和 fast 第一次相遇时：

$$ \text{slow 走过：} a + b $$$$ \text{fast 走过：} a + b + kL \quad (\text{某个整数 } k \geq 1) $$

因为 fast 是 slow 的两倍速度，$\text{fast} = 2 \cdot \text{slow}$，所以：

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

最后这个等式才是关键。它的意思是：从头节点走 $a$ 步会到入口；从相遇点也走 $a$ 步同样会到入口（因为 $(k-1)L$ 不过是绕几圈整环）。所以把 slow 拉回 head，两个指针都每次走一步，它们必然在入口处碰面。

LeetCode 19：删除倒数第 N 个节点

给你链表头，删除倒数第 n 个节点并返回新头。要求一趟扫描完成。
示例：head = [1,2,3,4,5]、n = 2 → [1,2,3,5]。

朴素做法两趟：先数出长度，再走到 length - n 那个位置。一趟扫描的关键技巧是「保持固定间距 $n + 1$ 的双指针」，再配合 dummy 节点，删头节点也不用特判。

 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 个节点。

    时间：O(L)，L 是链表长度。
    空间：O(1)。
    """
    dummy = ListNode(0, head)    # 用 dummy 统一处理"删头节点"
    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$？ 删除时我们要修改的是「目标节点的前驱」的 next，所以 slow 必须停在前驱上。如果 fast 只先走 $n$ 步，两者的间距是 $n$，fast 走到 None 时 slow 就直接停在了目标节点身上，没法删了。差一格是这道题最常见的 bug。

为什么需要 dummy？ 考虑 head = [1, 2]、n = 2（删头节点）。有 dummy 时：

fast 走 3 步到 None。
slow 还在 dummy。
dummy.next = dummy.next.next 让 dummy.next = 2。
返回 dummy.next = 2，搞定。

没 dummy 的话，你必须额外写 if n == length: return head.next，但要知道 length 又得先扫一遍——一趟扫描的目标就破产了。

LeetCode 146：LRU 缓存

设计一个数据结构，get(key) 和 put(key, value) 都要 $O(1)$ 摊还时间。容量满时淘汰最久未使用的键。

这道题在工业界出现的频率高得离谱——操作系统页缓存、CDN 边缘缓存、浏览器缓存、ORM 查询缓存，全是这套结构。标准答案是一个看似简单但极其优雅的组合：用哈希表做 $O(1)$ 查找，用双向链表维护「最近使用」顺序，两边互相引用。

为什么必须两个数据结构？

只用哈希表：查找 $O(1)$，但完全没办法表达「谁最近用过」。
只用链表：能维护顺序，但查找退化到 $O(n)$。
两个一起用：哈希表定位到节点（$O(1)$），再把节点从链表里摘下、挂到头部（双向链表所以是 $O(1)$）。

链表维护的不变量是：头部是最近使用的，尾部是最久未使用的。两个哨兵节点（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
60
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:
    """
    哈希表 + 双向链表 + 哨兵，实现 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

    # ----- 公开接口 -----

    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)

有三个细节值得停下来想一想：

哨兵节点不是可选的。 有了它，所有插入和删除都变成同一套四指针操作，代码里再没有 if head is None 这种东西。
节点本身要存 key。 淘汰最旧节点时要顺手把它的 key 从哈希表里删掉；如果节点不存 key，你只能反向遍历整个哈希表去找，那就不是 $O(1)$ 了。
get 时复用现有节点，不重新分配。 这才是真正的 $O(1)$ 摊还成本。生产环境如果用 dict + list.pop 重建，每次 get 都是 $O(n)$，看着对，跑起来慢一个数量级。

套路速查表

技术	什么时候用	本文对应题目
三指针（`prev` / `curr` / `next`）	原地反转或重连	反转链表
虚拟头节点 / 哨兵	头节点可能被改或要返回新头	合并、删除倒数第 N 个、LRU
快慢指针	找中点、检测环、找倒数第 k 个	环形链表 II、删除倒数第 N 个
哈希表 + 链表	既要 $O(1)$ 查找又要维护顺序	LRU 缓存
递归	操作天然有「分而治之」结构	递归反转、递归合并

常见坑

没判空就解引用。 curr.next.val 在 curr.next is None 的瞬间就崩。永远写成 while curr and curr.next:。
丢失前进路径。 写 curr.next = something 之前，如果还需要原来的 curr.next，先存到一个临时变量里（迭代反转里 nxt 这一行的全部意义就在这）。
忘了推进。 每次循环都必须至少有一个指针向终止条件移动，否则就是死循环。
间距差一格。 双指针固定间距的题，全看你 fast 先走的是 n 还是 n + 1。
不用 dummy 就硬写。 凡是头节点可能改变的操作，dummy 都能把 5 行的边界判断压缩到 0 行。

写在最后

链表题考的从来不是链表本身，考的是对状态变更的精确控制——给指针起对名字、把赋值排对顺序、永远不假设 next 字段非空。本文这五道题覆盖了你需要的所有套路：指针重连、虚拟头节点、快慢指针、间距双指针、哈希表 + 链表组合。

当你能不看任何参考默写出 reverseList、能在餐巾纸上证明 Floyd 算法为什么对，剩下的链表题就只是这些主题的变奏。下一篇我们从一维的指针链跳到二叉树，递归终于不再是花招而是天然语言。

LeetCode（三）—— 链表操作