# Linked List链表面试知识体系与记忆模板 核心原则**Array 用 indexLinked List 用 pointer。** 链表题的核心不是“访问元素”而是“移动和重新连接节点”。---## 1. 基本结构texthead↓[1] → [2] → [3] → [4] → Nonepythonclass ListNode:def __init__(self, val0, nextNone):self.val valself.next next两个基本操作pythonnode.valnode.next### Array vs Linked ListtextArray:arr[i]Linked List:node↓node.next↓node.next.next看到 Linked List 后第一反应 **不要想 index想 pointer。**---# 2. 四个核心 Primitive绝大多数 Linked List Medium 题都可以拆成textTraverse → Find Middle → Reverse → Merge / Reconnect其中最重要的模板text遍历 → curr curr.next找中点 → slow / fast找倒数位置 → fast / slow gap反转 → prev / curr / next合并 → dummy / tail删除 → prev.next curr.next---# 3. 基本遍历 Traversalpythoncurr headwhile curr:print(curr.val)curr curr.next记忆 **移动一个节点curr curr.next**---# 4. 找中点 Middle — Slow Fastpythonslow headfast headwhile fast and fast.next:slow slow.nextfast fast.next.next规律textslow1 stepfast2 steps常用于- Middle of Linked List- Reorder List- Palindrome Linked List- Merge Sort- Split Linked List记忆 **找中间一慢一快。**---# 5. 找倒数第 K 个节点核心让 fast 领先 slow 固定距离。pythonslow headfast headfor _ in range(k):fast fast.nextwhile fast:slow slow.nextfast fast.nextreturn slow记忆 **找倒数第 K 个Fast 先跑 K 步再一起走。**典型题- Remove Nth Node From End- Kth Node From End---# 6. Reverse Linked List这是必须做到肌肉记忆的模板。原始text1 → 2 → 3 → None目标text3 → 2 → 1 → None模板pythonprev Nonecurr headwhile curr:nxt curr.nextcurr.next prevprev currcurr nxtreturn prev为什么必须先保存 nxt因为pythoncurr.next prev会改变原来的 next。所以必须pythonnxt curr.next记忆口诀 **SAVE → REVERSE → MOVE**textSAVE:nxt curr.nextREVERSE:curr.next prevMOVE:prev currcurr nxt---# 7. Reverse 的三个核心变量textprev 已经反转好的部分curr 当前正在处理的节点nxt curr 原来的下一个节点看到 Reverse立即想到pythonprevcurrnxt---# 8. Split Linked List找到 middle 后pythonsecond slow.nextslow.next None例如text1 → 2 → 3 → 4 → 5↑slow切开text1 → 2 → 3 → None4 → 5 → None记忆 **Middle 找到以后slow.next None 才是真正切开。**---# 9. Merge Two Linked Lists两个链表textL1: 1 → 3 → 5L2: 2 → 4 → 6合并text1 → 2 → 3 → 4 → 5 → 6经典模板pythondummy ListNode()tail dummywhile l1 and l2:if l1.val l2.val:tail.next l1l1 l1.nextelse:tail.next l2l2 l2.nexttail tail.nexttail.next l1 or l2return dummy.next记忆 **Dummy 管起点Tail 管最后一个节点。**---# 10. Dummy Node当 head 可能变化时Dummy 可以统一处理边界。pythondummy ListNode(0, head)结构textdummy → 1 → 2 → 3最终pythonreturn dummy.next常用于- Merge Two Sorted Lists- Remove Nodes- Partition List- Remove Nth Node From End记忆 **Head 麻烦就加 Dummy。**---# 11. Pointer Manipulation链表真正操作的是 nextpythonnode.next another_node例如text1 → 2 → 3执行pythonnode1.next node3会改变链路。因此看到 reorder / reverse / remove / merge / insert第一反应 **我要怎么修改 next**---# 12. Reorder List例如text1 → 2 → 3 → 4 → 5目标text1 → 5 → 2 → 4 → 3不要理解成 Sorting。正确拆解textReorder↓① Find Middle↓② Split↓③ Reverse Second Half↓④ Merge Alternately例如text1 → 2 → 3 | 4 → 5↓Reverse↓1 → 2 → 3 | 5 → 4↓Merge↓1 → 5 → 2 → 4 → 3记忆 **Reorder Middle Reverse Merge**---# 13. Palindrome Linked List例如text1 → 2 → 3 → 2 → 1核心textFind Middle↓Reverse Second Half↓Compare即 **Palindrome Middle Reverse Compare**---# 14. Cycle Detection判断有没有环pythonslow headfast headwhile fast and fast.next:slow slow.nextfast fast.next.nextif slow fast:return Truereturn False核心textslow1 stepfast2 steps有环 fast 最终会追上 slow。无环 fast 最终到 None。注意pythonslow fast比较的是节点而不是pythonslow.val fast.val记忆 **Cycle Slow/Fast 相遇。**---# 15. Find Cycle Entry第一阶段找到相遇点。第二阶段pythonslow headwhile slow ! fast:slow slow.nextfast fast.nextreturn slow记忆 **相遇 → 一个指针回 Head → 两个一起走 → 再次相遇就是入口。**---# 16. Intersection of Two Linked Lists两个链表textA: 1 → 2 ┐↓7 → 8↑B: 4 → 5 ┘经典pythona headAb headBwhile a ! b:a a.next if a else headBb b.next if b else headAreturn a思想 两个 pointer 都走 A B最终拥有相同总路径长度。注意pythona b不是pythona.val b.val因为 intersection 指的是 **同一个 Node object。**记忆 **Intersection 两条路互换起点。**---# 17. Remove Nth Node From End核心textFast 先走 N 步↓Slow Fast 一起走↓Slow 停在删除节点的前一个位置常用 Dummypythondummy ListNode(0, head)slow dummyfast dummyfor _ in range(n):fast fast.nextwhile fast.next:slow slow.nextfast fast.nextslow.next slow.next.nextreturn dummy.next记忆 **删除倒数第 N 个Fast 先跑 N 步Slow 找前驱。**---# 18. Partition List例如text3 → 5 → 2 → 1 → 4x 3目标text2 → 1 → 3 → 5 → 4建立两条链textsmall listlarge list分别使用 Dummy Tail。最后textsmall → large记忆 **Partition 两条链 → 最后拼起来。**---# 19. Copy List With Random Pointer节点除了pythonvalnext还有pythonrandom核心难点 random 可以指向任意节点。最容易掌握的方法pythonold_to_new {}第一遍pythoncurr headwhile curr:old_to_new[curr] Node(curr.val)curr curr.next第二遍pythoncurr headwhile curr:old_to_new[curr].next old_to_new.get(curr.next)old_to_new[curr].random old_to_new.get(curr.random)curr curr.next记忆 **复杂指针 → Old Node 映射到 Copy Node。**---# 20. Add Two Numbers链表表示数字例如text2 → 4 → 3代表text342核心就是竖式加法pythoncarry 0while l1 or l2 or carry:x l1.val if l1 else 0y l2.val if l2 else 0total x y carrydigit total % 10carry total // 10再用 Dummy Tail 构造答案。记忆 **Linked List Addition Digit Carry。**---# 21. Merge Sort on Linked List完整流程textFind Middle↓Split↓Sort LeftSort Right↓Merge递归终止pythonif not head or not head.next:return head核心 **Linked List Merge Sort Middle Recursion Merge**时间复杂度textO(n log n)---# 22. Doubly Linked List双向链表textNone ← [1] ⇄ [2] ⇄ [3] → None节点pythonclass Node:def __init__(self, key, val):self.key keyself.val valself.prev Noneself.next None两个方向pythonnode.prevnode.next记忆 **Singly只知道后面。** **Doubly知道前面 后面。**---# 23. LRU Cache经典组合textLRU Cache│├── HashMap│ ↓│ O(1) lookup│└── Doubly Linked List↓O(1) remove / insertHashMaptextkey → nodeDoubly Linked List 维护最近使用顺序。记忆 **LRU HashMap 找节点 Doubly Linked List 管顺序。**---# 24. 高频复杂度| 操作 | Singly Linked List ||---|---:|| Access by index | O(n) || Search | O(n) || Insert at head | O(1) || Delete head | O(1) || Insert after known node | O(1) || Delete after known node | O(1) || Find middle | O(n) || Reverse | O(n) || Merge | O(n m) |最重要textArray:Random Access O(1)Linked List:Random Access O(n)---# 25. Linked List 高频 Pattern 总表| 问题 | 第一反应 ||---|---|| 遍历 | curr curr.next || 找中点 | Slow Fast || 找倒数第 K 个 | Fast ahead K || 判断 Cycle | Slow Fast || 找 Cycle Entry | 相遇后一个回 Head || Reverse | Prev Curr Next || Merge | Dummy Tail || Delete | Prev Next || Reorder | Middle Reverse Merge || Palindrome | Middle Reverse Compare || Intersection | 两个 Pointer 交换 Head || Partition | 两条链 Merge || Random Pointer | HashMap || Add Two Numbers | Carry Dummy || Sort | Merge Sort || LRU | HashMap Doubly Linked List |---# 26. 做题时的“10 秒诊断模型”看到 Linked List 题先不要写代码问text① 是不是要找 Middle→ Slow / Fast② 是不是要找倒数位置→ Fast 先走 K 步③ 是不是要 Reverse→ Prev / Curr / Next④ 是不是要 Delete→ Prev.next Curr.next⑤ 是不是要 Merge→ Dummy / Tail⑥ 是不是要 Reorder→ Split Reverse Merge⑦ 是不是要判断 Cycle→ Slow / Fast⑧ 是不是要找 Intersection→ 两个 Pointer 交换 Head⑨ 是不是有 Random Pointer→ HashMap⑩ 是不是需要 O(1) lookup 顺序维护→ HashMap Doubly Linked List---# 27. 一分钟记忆卡## Linked List Pointer ProblemtextArray:indexLinked List:pointer## 五大基础模板### 1. Traversepythoncurr curr.next### 2. Middlepythonslow slow.nextfast fast.next.next### 3. Reversepythonnxt curr.nextcurr.next prevprev currcurr nxt### 4. Mergepythontail.next nodetail tail.next### 5. Deletepythonprev.next curr.next---# 28. 最终心智模型textLINKED LIST│┌─────────────┼─────────────┐↓ ↓ ↓POSITION DIRECTION STRUCTURE│ │ │↓ ↓ ↓Slow / Fast Reverse Merge/Delete│ │ │↓ ↓ ↓Middle/Kth Prev/Curr Dummy/Tail│↓Reconnect最重要的三句话 **1. Linked List 不靠 index靠 pointer。** **2. 改链表不是改 value而是改 next。** **3. 大多数 Medium 题都是 Middle / Reverse / Merge / Pointer Manipulation 的组合。**---# 29. Reorder List 的最终记忆你刚才正在做的题可以压缩成textReorder ListMiddle↓Split↓Reverse second half↓Merge alternately一句话 **找中点 → 切开 → 后半反转 → 两边交替合并。**它不是一个需要单独死记的题。它是textSlow/FastSplitReverseMerge四个 Linked List 基础 Primitive 的组合。