链表

链表由一个个节点通过指针串成，元素不必在内存中连续，因此插入删除快、随机访问慢，与数组正好互补。它是面试数据结构题的高频考点：反转链表、环形检测、合并有序链表几乎是必刷题，理解指针操作是第一步。

节点与基本结构

每个节点存数据和一个指向下一节点的指针，最后一个节点指向空：

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.nxt = nxt

head = Node(1, Node(2, Node(3)))    # 1 -> 2 -> 3 -> None

def traverse(head):                 # 从头遍历打印
    cur = head
    while cur:
        print(cur.val, end=" ")     # 输出：1 2 3
        cur = cur.nxt

traverse(head)

链表的灵魂在"改指针"：删除节点要让前驱的 nxt 绕过它；插入节点要先接新节点、再断旧链，顺序写反就会丢节点。

复杂度与数组对比

操作	数组	链表
随机访问	O(1)	O(n)（需从头走）
头插/头删	O(n)（搬移）	O(1)
尾插/尾删	均摊 O(1)	O(n)（需遍历，除非带尾指针）
中间插入	O(n)（搬移）	O(n)（先找到位置，改指针 O(1)）
额外内存	少	每节点多一个指针

高频结论：已知待操作节点的前驱时，链表插入删除是 O(1)；数组则是 O(n)。这也是 LRU 缓存用"哈希表 + 双向链表"的原因——哈希 O(1) 定位节点，链表 O(1) 完成移动与淘汰。

经典操作一：反转链表

逐个把当前节点的指针掉头，需要三个指针 prev/cur/nxt 配合：

def reverse(head):
    prev = None
    while head:
        nxt = head.nxt        # 先保存后继
        head.nxt = prev       # 指针掉头
        prev, head = head, nxt
    return prev               # 原链尾成为新头

# 1 -> 2 -> 3 反转后：3 -> 2 -> 1

反转是链表面试的"母题"：K 个一组反转、回文链表判断都会用到它，务必能默写迭代与递归两种写法。

经典操作二：环形检测（快慢指针）

快指针每次走两步、慢指针走一步；若有环二者必在环中相遇，否则快指针先到空：

def has_cycle(head):
    slow = fast = head
    while fast and fast.nxt:
        slow = slow.nxt
        fast = fast.nxt.nxt
        if slow is fast:
            return True
    return False

判断环的起点（入口节点）是进阶题：相遇后让一个指针回到头，两指针各走一步再次相遇处即环入口，数学推导基于"快指针多走的路程是环长的整数倍"。

经典操作三：合并两个有序链表

用哨兵（dummy）节点避免处理空头，谁小接谁：

def merge(l1, l2):
    dummy = tail = Node(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.nxt = l1; l1 = l1.nxt
        else:
            tail.nxt = l2; l2 = l2.nxt
        tail = tail.nxt
    tail.nxt = l1 or l2       # 接上剩余部分
    return dummy.nxt

dummy 节点是链表题的通用技巧：当头节点可能被删除或替换（如反转结果、合并结果）时，用哑节点占位可省去大量"头为空"的分支判断。

小结

链表的本质是"用指针换灵活性"：无搬移的插入删除换来 O(n) 查找。把节点连接、反转、快慢指针、dummy 哨兵四个基本功练熟，绝大多数链表题都能拆成它们的组合。