链表核心操作

链表与数组的差异

链表节点分散在堆上，通过 next 指针连接。插入/删除已知节点 O(1)，但 按索引访问 O(n)。面试高频：反转、合并、环、相交、重排、K 组反转。

画图是链表题第一技能：标出 dummy 头结点、prev/curr/next 三指针，避免断链。

虚拟头结点 dummy

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

dummy 统一处理「删头节点」边界，减少分支。

反转链表

迭代：

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

递归：先反转子链，再把当前节点接到子链末尾。注意栈深 O(n)。

快慢指针

• 找中点：快 2 慢 1，用于归并排序链表、回文判断。
• 倒数第 k 个：快指针先走 k 步，再同速走，快到头时慢在目标前驱。
• 环检测：见 week01-two-pointers Floyd 算法。

合并与重排

合并两个有序链表：比较 l1.val 与 l2.val，小者接入，指针前进。

合并 K 个有序链表：小根堆维护 K 个头，每次 pop 最小 push 其 next；复杂度 O(N log K)。

重排链表（L0→Ln→L1→Ln-1…）：找中点、反转后半、交替合并。

相交链表

两链长度差 d：长链指针先走 d 步，再同步走，相遇即交点（或 None）。本质：对齐后同时前进。

Go 侧提示

Go 无内置链表类型，面试手写 type Node struct { Val int; Next *Node }。注意 nil 判断与 dummy := &ListNode{} 模式。Week 2 后续 week02-go-slice-map 对比 slice 与链表的内存布局。

面试 checklist

• 是否修改原链还是新建？
• 环、空链、单节点。
• 画图验证指针没有丢失后半段。

建议刷：206 反转、141 环、21 合并、142 环入口、19 删除倒数第 N。配合 /chapters/algorithm-lab/problems 巩固。

实战巩固与面试表达

本篇属于 8 周冲刺 week02-linked-list 主题。复习时先闭卷回答 frontmatter 中三张 flashcard，再展开口述两个「为什么」：为什么这种方案能 work、边界失败时如何降级。与相邻章节对照：算法篇强调复杂度与模板，Go 篇强调工程默认写法，中间件篇强调线上故障案例。

动手与自检清单

用 25 分钟限时做 1 道相关练习题或画出一张架构/数据结构示意图；用 5 分钟写 STAR 片段说明你在项目里是否用过类似技术。记录 3 个面试追问及你的标准答法，存入 /zh/notebook/master-plan 笔记。若某点不熟，回到对应 /chapters 交互 Lab 重新走一遍流程，比死记卡片更有效。

易错点提醒

避免只背名词不会画图；避免只说优点不谈 trade-off（性能、一致性、运维成本至少提一项）；避免把学习 Demo 说成百万 QPS 生产。回答时使用「场景 → 方案 → 结果 → 反思」四段式，体现工程成熟度。