2.2 链表：指针串起的散装功法

2.2 链表：指针串起的散装功法

本节摘要：链表把元素装进一个个散居内存的节点，靠"next 引用"串成一条线。它放弃了数组的地址算术（按下标访问退化成 O(n)），换来插删的自由——只要握住前驱节点，摘除或接上仅需改一两个引用、O(1) 完成。本节实现单链表的三板斧（建、插、删与反转、快慢指针），并对照三种变体的适用场景。

让节点散居，用指针牵手

数组的全部优势来自"连续"，全部枷锁也来自"连续"。链表反其道而行：每个元素住一个小盒子（节点），盒子里除了数据还放一个引用指向下一个盒子。想在下图中间插一个新节点？不需要搬移任何人，只要让左边节点的引用改指新节点、新节点指向右边节点——两次改写，完事。

单链表、双向链表与循环链表

先用类把节点与最基本的建表、遍历、按下标访问写出来，顺便数步数验证"随机访问退化"：

# 单链表基本功：建表、遍历、按下标访问（数步数）
class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt          # 指向下一个节点，末节点指向 None

def build(values):                # 尾插法：保持读序与插入序一致
    head = Node(0)               # 哨兵节点，省去对空表的特殊判断
    tail = head
    for v in values:
        tail.next = Node(v)
        tail = tail.next
    return head

def walk(head):
    cur, out = head.next, []
    while cur:
        out.append(cur.val)
        cur = cur.next           # 每读一个节点走一步
    return out

def get(head, i):                # 按下标访问：从头部走 i 步
    cur, steps = head.next, 0
    while cur and steps < i:
        cur = cur.next
        steps += 1
    return cur.val if cur else None, steps

head = build([11, 22, 33, 44, 55])
print("遍历结果：", walk(head))
# 输出：遍历结果： [11, 22, 33, 44, 55]
for i in (0, 2, 4):
    val, steps = get(head, i)
    print(f"取下标 {i}：值 = {val}，走了 {steps} 步")
# 输出：
# 取下标 0：值 = 11，走了 0 步
# 取下标 2：值 = 33，走了 2 步
# 取下标 4：值 = 55，走了 4 步
​

同样的下标，数组一乘一加直达，链表要走 i 步——按下标访问是 O(n)。这是链表为插删自由付出的头号代价。

反转链表：三引用轮转，一步不虚

链表最经典的招式是原地反转：维护 prev、cur、nxt 三个引用，每轮把 cur 的指向掰向 prev，然后整体右移一格。

# 反转链表：每轮改一次指向，移一次站位
def reverse(head):
    prev, cur = None, head.next
    rounds = 0
    while cur:
        nxt = cur.next           # 先记住后路
        cur.next = prev          # 掉头：当前节点改指前驱
        prev, cur = cur, nxt     # prev 与 cur 各前进一步
        rounds += 1
    head.next = prev             # 哨兵改接新头（原尾节点）
    return head, rounds

head = build([1, 2, 3, 4])
head, rounds = reverse(head)
print("反转后：", walk(head), "，共", rounds, "轮")
# 输出：反转后： [4, 3, 2, 1] ，共 4 轮
# 每个节点恰好掉头一次，n 个节点 n 轮，O(n) 时间、O(1) 额外空间
​

顺手的第二板斧是快慢指针找中点：慢指针每步走一格、快指针走两格，快指针到尾时慢指针恰在中点。一趟扫描、两个引用，空间 O(1)：

# 快慢指针找中点
def middle(head):
    slow = fast = head.next
    while fast and fast.next:
        slow = slow.next         # 慢指针一格
        fast = fast.next.next    # 快指针两格
    return slow.val

head = build([1, 2, 3, 4, 5, 6, 7])
print("七个节点的中点值 =", middle(head))
# 输出：七个节点的中点值 = 4
# 快指针 1→3→5→7 共走 3 大步到尾，慢指针同步走 3 小步，停在下标 3（第 4 个节点）
​

三种变体的分工与对表

单链表只知道后继，想删"当前节点"必须先找到前驱（从头部再走一遍）；双向链表每个节点多存一个 prev 引用，前驱后继都握在手里，删任意节点严格 O(1)，代价是每节点多一份引用内存与每次插删多改两条指向。循环链表把尾接回头，天然适合"轮转调度"类任务——约瑟夫环问题、操作系统时间片轮转的环形队列，都靠"没有天然终点"这一性质省掉回头的判断。

语言内置容器早就替你选好了：Python 的 list 是动态数组；Java 的 LinkedList 是双向链表、ArrayList 是动态数组；C++ 的 list 是双向链表。频繁两头进出选链表系，频繁随机访问选数组系，这张表就是选型依据。

⚠️ 常见坑：头插法建表会让读序与插入序颠倒——依次头插 1、2、3，遍历得到的是 3、2、1。读序必须与插入序一致时用尾插法（如上面 build 的写法）。

走火入魔：指针纪律三则

**事故一：弄丢入口。**链表只能从 head 进入。head = head.next 写进循环里腾挪几次，前半段节点再无引用可达，在 C 里是内存泄漏，在 Java 与 Python 里只能等垃圾回收。纪律：改任何指向之前，先用临时引用把后路存好，reverse 演示里的 nxt = cur.next 就是保命符。

**事故二：循环链表里用"是否为 None"判终点。**循环链表没有 None，判空条件该用"是否回到起点"。沿用单链表的判断会无限打转。变体改的是心法前提，招式（遍历写法）必须跟着改。

**事故三：双向链表少改一条指向。**双向链表的插删要同时维护 next 与 prev 两条线，只改一条会让表在"正向走"与"反向走"时呈现两个世界。写完双向链表的操作，正反各遍历一遍再收工。

💡 关键直觉：链表的复杂度全部围绕"你握着哪个节点"展开——握住前驱，插删 O(1)；只握住头，一切按位置的操作都是 O(n)。工程上常配一个哈希表把"关键字映射到节点"，把两条世界的优势拼起来，第 7 章的 LRU 缓存正是这个组合。

本节要点回顾

• 链表的心法：节点散居、引用牵手；放弃地址算术换来插删自由，已知前驱时插删严格 O(1)；
• 按下标访问退化成 O(n)：数步数实验显示取下标 i 恰好走 i 步，这是与数组最本质的分野；
• 三板斧：尾插建表保读序、三引用轮转原地反转（n 轮 O(n)）、快慢指针一趟找中点；
• 变体分工：双向链表删已知节点 O(1) 但每节点双引用；循环链表适合轮转调度；
• 指针纪律：改指向先存后路、循环表不用 None 判终点、双向表正反各验一遍。

线条排好之后，接下来两种结构只在一处动刀：限制进出的"那一头"。先看只许后进先出的栈。