链表 解题模板

适用场景

链表操作：反转、合并、环检测、删除、排序

通用模板

反转链表

 
# 迭代（四步口诀）
 
prev, curr = None, head
 
while curr:
 
    nxt = curr.next          # 1. 记后面
 
    curr.next = prev         # 2. 回头
 
    prev, curr = curr, nxt   # 3. 前移 4. 当前移
 
return prev
 
# 递归
 
def reverse(head):
 
    if not head or not head.next: return head
 
    new_head = reverse(head.next)
 
    head.next.next = head
 
    head.next = None
 
    return new_head
 

快慢指针

 
# 找中点 / 检测环
 
slow = fast = head
 
while fast and fast.next:
 
    slow = slow.next
 
    fast = fast.next.next
 
    if slow == fast:  # 有环
 
        # 找环入口：slow = head, 同步走直到相遇
 

哑节点（简化头处理）

 
dummy = ListNode(0)
 
dummy.next = head
 
# ... 对链表操作 ...
 
return dummy.next
 

复杂度总结

模式	时间	空间	典型题
反转	O(n)	O(1)	反转链表、K个一组反转
快慢指针	O(n)	O(1)	环检测、找中点、相交链表
归并合并	O(n)	O(1)	合并有序链表、排序链表
递归	O(n)	O(n)	反转、合并

关键要点

• 反转必会迭代：递归也可以但空间 O(n)

• 哑节点：避免头节点特殊处理

• 快慢指针初始化是否同起点？

• 环形链表 II：双阶段 Floyd

→ 查看该分类题目：LeetCode学习路线图 > 四、链表

---

相似题对比

易混题对	关键区别	解法差异
206反转链表 vs 92反转链表II	全反转 vs 区间反转	206 四步口诀；92 需要先走到 left-1
141环形链表 vs 142环形链表II	判环 vs 找入口	141快慢相遇则True；142阶段2找入口
21合并有序链表 vs 23合并K个升序链表	两路 vs K路	21递归/迭代；23分治/堆
82删除重复II vs 83删除重复	全删 vs 留一个	82只需控制前驱指针
19删除倒数第N vs 61旋转链表	一个指针先走N步 vs k%n找新头	都是快慢指针变体

---

测试用例模板

 
# 基础功能
 
assert list_to_array(reverseList(arr_to_list([1,2,3,4,5]))) == [5,4,3,2,1]
 
assert list_to_array(reverseList(arr_to_list([1,2]))) == [2,1]
 
# 边界
 
assert reverseList(None) == None                # 空链表
 
assert reverseList(ListNode(1)).val == 1        # 单节点
 

---

关联题型

关联题型	常见结合方式	典型题目
数组与哈希	哈希表存节点引用	141环形链表, 160相交链表
设计题	链表实现LRU/LFU缓存	146LRU缓存
栈	双栈/快慢指针	234回文链表