链表

Vol 2：算法森林探险 · 链表特辑

---

遭遇战：弯弯曲曲的小路

上一章走了笔直的数组路。现在该看木牌 B——弯弯绕绕的小路，棚屋散落山坡各处，靠细绳串在一起。驿站随时变动，新棚屋今天开，老棚屋明天塌。

没有下标地图。 找第 17 个棚屋，从第一个开始数。这就是链表。

---

什么是链表？

节点散落在内存各处，每个节点拿着下一节点的地址：

[1] → [2] → [3] → [4] → None

单链表节点

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
cur = head
while cur:
    print(cur.val, end=" → ")
    cur = cur.next
# 输出: 1 → 2 → 3 → None

查找 O(n)

数组一步到位。链表？从第 1 个数过去：

def get_kth(head, k):
    for _ in range(k):
        if not head: raise IndexError
        head = head.next
    return head

复杂度 O(k)，最坏 O(n)。

插入/删除 O(1)

数组中间插入要右移——O(n)。链表只需改线：

def insert_after(prev, val):
    new_node = ListNode(val)
    new_node.next = prev.next
    prev.next = new_node

def delete_after(prev):
    if prev and prev.next:
        prev.next = prev.next.next

关键：已站在插入点时，改两条线就是 O(1)。

---

双链表 & 循环链表

加 prev 指针→双链表（反向遍历 O(n)，内存翻倍）。尾节点回头→循环链表（轮询调度、约瑟夫环）。

哨兵节点简化边界

def remove_node(head, val):
    dummy = ListNode(0)
    dummy.next = head
    cur = dummy
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

没有特例了——所有节点处理一致。

---

常见陷阱

说法	真相
"链表插入 O(1) 所以比数组快"	只在已站到插入点成立。找点本身 O(n)
"链表不浪费空间"	每个节点多存指针+对象头，通常更吃内存
"Python 有链表库"	无默认库。Java 有 LinkedList<E>，C++ 有 forward_list

---

通关挑战

1. 单链表反转（in-place）
2. 合并两个有序链表
3. 快慢指针找中间节点

---

验收标准

• [ ] 能手写链表定点插入/删除（O(1)）
• [ ] 能画链表内存分布（散落 + next 串联）
• [ ] 能区分单链表、双链表、循环链表
• [ ] 能解释哨兵节点作用

---

旅人笔记

链表是对立面的艺术——牺牲随机访问，换来定点插入/删除。面试高频：反转、合并、找环、找中点。这四个覆盖 90% 链表题。

---

→ 下一站预告

上一章：数组 | 对比参考页

已经会了连续与离散。下一站变成两种容器——第3章：栈与队列。

继续阅读：栈与队列 →