04 · 链表

来源： labuladong 链表框架 + 代码随想录链表专题
核心价值： 掌握指针操纵——链表题的灵魂就是”改指针”
题量： 14 题（Hot 100 中题量最大的数据结构）

---

一、本质理解

labuladong 将链表的本质定义为 离散存储的线性结构，与之相对的是数组的连续存储。

对比	数组	链表
存储方式	连续内存	离散内存（通过指针链接）
随机访问	O(1)	O(n)
插入/删除	O(n)	O(1)（已知位置时）
额外空间	无	O(n) 的指针存储

核心思维： 链表题的每一步操作都是在 改指针，画图是关键！

---

二、链表专题概览

链表基础（Day 4）
├── 虚拟头节点（dummy）：统一头节点处理
├── 快慢指针：判环、找中点、找倒数第 k 个
├── 链表翻转：pre, cur, nxt 三指针
├── 合并有序链表：虚拟头 + 双指针
└── 相交链表：浪漫双指针法

链表进阶（Day 5）
├── 递归翻转：K 个一组翻转链表
├── 分治合并：归并排序思想
├── 复制带随机指针：三步法
└── LRU 缓存：哈希表 + 双向链表

---

三、核心模板

模板 1：虚拟头节点（统一边界）

dummy = ListNode(0, head)
# 操作链表时始终用 dummy.next 取头节点
return dummy.next

模板 2：链表翻转（三指针法）

def reverse_list(head):
    pre = None
    cur = head
    while cur:
        nxt = cur.next   # 保存下一个节点
        cur.next = pre   # 反转指针
        pre = cur        # pre 前移
        cur = nxt        # cur 前移
    return pre  # 新头节点

模板 3：合并有序链表

def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2
    return dummy.next

模板 4：找倒数第 K 个节点（快慢指针）

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    # fast 先走 n+1 步
    for _ in range(n + 1):
        fast = fast.next
    # fast 到尾时，slow 指向待删节点的前一个
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

模板 5：K 个一组翻转链表

def reverse_k_group(head, k):
    dummy = ListNode(0, head)
    pre = dummy
    
    while True:
        # 检查是否有 k 个节点
        cur = pre
        for _ in range(k):
            cur = cur.next
            if not cur:
                return dummy.next
        
        # 翻转 k 个节点
        group_head = pre.next
        next_group = cur.next
        pre.next = reverse_sublist(group_head, k)
        group_head.next = next_group
        pre = group_head
 
def reverse_sublist(head, k):
    pre = None
    cur = head
    for _ in range(k):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    return pre

---

四、LRU 缓存（必考！哈希表 + 双向链表）

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        # 虚拟头尾节点
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)
        return node.value
    
    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]
    
    def _add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def _remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)
    
    def _remove_tail(self):
        node = self.tail.prev
        self._remove_node(node)
        return node

---

五、Hot 100 链表题目清单

Day 4：链表基础

题号	题目	难度	核心技巧	建议用时
160	相交链表	Easy	双指针浪漫法	25 min
206	反转链表	Easy	三指针翻转	20 min
234	回文链表	Easy	找中点 + 翻转后半	30 min
141	环形链表	Easy	快慢指针判环	20 min
142	环形链表 II	Medium	Floyd 找环入口	35 min
21	合并两个有序链表	Easy	虚拟头 + 双指针	25 min
2	两数相加	Medium	模拟竖式加法	30 min
19	删除倒数第 N 个	Medium	快慢指针 + 虚拟头	30 min

Day 5：链表进阶

题号	题目	难度	核心技巧	建议用时
24	两两交换节点	Medium	虚拟头 + 画图	30 min
25	K 个一组翻转	Hard	分组翻转 + 组间重连	45 min
138	随机链表复制	Medium	插入克隆 + 拆分	35 min
148	排序链表	Medium	归并排序（找中点+合并）	40 min
23	合并 K 个链表	Hard	分治/最小堆	40 min
146	LRU 缓存	Medium	哈希表+双向链表	45 min

---

六、易错点与技巧

1. 画图！画图！画图！ 链表操作必须画图，否则很容易指针乱指
2. 虚拟头节点：90% 的链表题可以用 dummy 简化边界处理
3. 空指针检查：始终检查 node 和 node.next 是否为 None
4. 断链与重连：修改指针前先保存下一节点 nxt = cur.next
5. 快慢指针初始化：判环时 slow = fast = head；找中点时也相同

---

七、复杂度总结

操作	时间复杂度	空间复杂度
翻转链表	O(n)	O(1) 或 O(n) 递归栈
快慢指针	O(n)	O(1)
合并有序链表	O(n)	O(1)
LRU 操作	O(1)	O(capacity)

---

八、参考与延伸

• 02-双指针与滑动窗口（快慢指针在数组中的应用）
• labuladong 链表框架：https://labuladong.online/algo/
• 代码随想录链表专题：https://programmercarl.com/