链表、栈与队列¶
链表、栈和队列是更复杂数据结构的构建块。本篇将讲解它们的机制，然后通过逐渐深入的问题，构建关键模式：快慢指针、单调栈以及基于堆的优先队列，并在每一步指出常见陷阱。
- 数组提供了快速的随机访问，但插入代价高昂。链表提供了快速的插入，但没有随机访问。栈和队列将访问限制在一端或两端，而这种限制正是它们强大的原因：通过限制你能做的事情，它们简化了你需要思考的内容。
链表¶
- 单向链表 是一个节点链。每个节点存储一个值和一个指向下一个节点的指针。最后一个节点指向
null。
-
相对于数组的优势：在已知位置插入或删除的时间复杂度为 \(O(1)\)（只需重定向指针）。不需要移动元素。
-
劣势：访问第 \(i\) 个元素需要 \(O(i)\) 次遍历（没有随机访问）。缓存局部性差（节点散落在内存中）。
-
双向链表 增加了
prev指针，支持向后遍历。用于 LRU 缓存（常数时间删除任意节点）和浏览器历史（后退/前进）。
| 操作 | 单向 | 双向 |
|---|---|---|
| 按索引访问 | \(O(n)\) | \(O(n)\) |
| 头部插入 | \(O(1)\) | \(O(1)\) |
| 尾部插入 | \(O(n)\) 或 \(O(1)\)* | \(O(1)\) |
| 删除给定节点 | \(O(n)\)** | \(O(1)\) |
| 查找 | \(O(n)\) | \(O(n)\) |
有尾指针时。*需要前驱节点，这需要遍历。
- 哨兵节点（哑头/哑尾）简化了边界情况。没有哑头时，头部插入或删除需要特殊处理。使用哑节点后，每个真实节点都有前驱。
# 无哑节点：头删除需要特殊处理
def delete_head(head):
if not head:
return None
return head.next
# 有哑节点：统一逻辑
dummy = ListNode(0)
dummy.next = head
# 现在所有删除都是：prev.next = prev.next.next
- 陷阱：忘记处理空链表（
head is None）或只有一个元素的链表。务必测试这些边界情况。
模式：快慢指针（Floyd 判圈算法）¶
- 使用两个以不同速度移动的指针来检测链表的属性。慢指针一次移动一步；快指针一次移动两步。
简单：环形链表¶
-
问题：判断一个链表是否有环。
-
模式：如果有环，快指针最终会追上慢指针（它们会相遇）。如果没有环，快指针会到达
null。
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
-
为什么有效：如果环的长度为 \(c\)，快指针每步将距离缩小 1 个节点。从慢指针进入环开始，它们一定会在 \(c\) 步内相遇。
-
陷阱：检查
fast and fast.next（而不仅仅是fast.next）。如果fast是None，调用fast.next会崩溃。
中等：寻找链表的中间节点¶
-
问题：返回中间节点。
-
模式：当快指针到达末尾时，慢指针就在中间。
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow 在中间（如果长度为偶数，返回第二个中间节点）
中等：环形链表 II（寻找环的入口）¶
-
问题：返回环开始的节点。
-
模式：在快慢指针相遇后，将其中一个指针重置到头节点。两个指针都以速度 1 移动。它们会在环的入口处相遇。
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# 将一个指针重置到头节点
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
- 为什么有效：设头节点到环入口的距离为 \(a\)，环入口到相遇点的距离为 \(b\)。慢指针走了 \(a + b\)。快指针走了 \(2(a + b)\)。差值正好是一个环：\(a + b = c\)（环长）。所以 \(a = c - b\)：头节点到环入口的距离等于从相遇点继续前进到环入口的距离（沿环方向）。
困难：K 个一组反转链表¶
- 问题：将链表中每 \(k\) 个连续节点反转。
def reverse_k_group(head, k):
# 检查是否还剩 k 个节点
node = head
for _ in range(k):
if not node:
return head
node = node.next
# 反转 k 个节点
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# head 现在是反转组的新尾节点
# 递归处理剩余部分
head.next = reverse_k_group(curr, k)
return prev # prev 是该组的头节点
- 陷阱：原地反转模式 (
prev, curr, nxt) 值得记住。画出来：每一步把curr.next指向prev，然后前进三个指针。弄错顺序会破坏链表。
栈¶
-
栈 是 LIFO（后进先出）：最后添加的元素最先被移除。想象一叠盘子。
-
操作：
push(x)添加到顶部，pop()从顶部移除，peek()查看顶部但不移除。都是 \(O(1)\)。 -
栈是递归（调用栈）、表达式求值（中缀转后缀）和撤销操作（每次操作入栈，撤销时弹出上一个）背后的隐式结构。
简单：有效的括号¶
-
问题：给定一个由括号
()[]{}组成的字符串，判断它们是否平衡。 -
模式：将左括号压入栈。当遇到右括号时，检查栈顶是否是对应的左括号。
def is_valid(s):
stack = []
matching = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
- 陷阱：忘记最后检查
len(stack) == 0。字符串 "(((" 没有不匹配，但因为有未闭合的左括号，所以不是有效的。
模式：单调栈¶
-
单调栈 维护元素的有序顺序（递增或递减）。当新元素会破坏顺序时，弹出元素直到恢复顺序。
-
何时使用：问题要求“对每个元素，找到下一个/上一个更大/更小的元素”。栈总共只需 \(O(n)\) 时间，因为每个元素最多入栈和出栈一次。
中等：每日温度¶
-
问题：给定每日温度，对每一天，找出需要等多少天才能遇到更高的温度。
-
模式：使用存储索引的栈。当当前温度高于栈顶索引对应的温度时，弹出并记录距离。
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # 存储索引，温度递减
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev = stack.pop()
result[prev] = i - prev
stack.append(i)
return result
-
每个元素入栈一次，最多出栈一次：总共 \(O(n)\)。
-
陷阱：栈中存储的是索引（而不是值）。你需要索引来计算距离。
困难：柱状图中最大的矩形¶
-
问题：给定一个柱状图的高度数组，找出最大矩形的面积。
-
模式：对每个柱子，找出它向左和向右能延伸多远（即左右两侧第一个比它矮的柱子的位置）。一个单调递增栈能高效地跟踪这些信息。
def largest_rectangle(heights):
stack = [] # 存储 (起始索引, 高度)，高度递增
max_area = 0
heights.append(0) # 哨兵，最后清空栈
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
idx, height = stack.pop()
max_area = max(max_area, height * (i - idx))
start = idx # 当前柱子的左边界可以扩展到被弹出柱子的起始位置
stack.append((start, h))
heights.pop() # 移除哨兵
return max_area
-
陷阱：
start = idx这行很微妙。当我们弹出一个比当前柱子高的柱子时，当前柱子可以向左扩展到被弹出柱子的起始位置（因为两者之间的所有柱子都至少和被弹出柱子一样高）。缺少这一行会导致面积计算错误。 -
陷阱：哨兵
heights.append(0)确保栈中剩余的柱子都被处理。没有它，那些右边从未遇到更矮柱子的柱子会被遗漏。
队列¶
-
队列 是 FIFO（先进先出）：元素在后端添加，从前端移除。想象商店里排队。
-
双端队列 支持在两端进行 \(O(1)\) 的插入和删除。Python 的
collections.deque是标准实现。 -
队列是 BFS（广度优先搜索）、任务调度 和 消息传递 背后的结构。
简单：用栈实现队列¶
-
问题：仅使用两个栈来实现队列。
-
模式：一个栈用于入队，一个栈用于出队。当出队栈为空时，将所有元素从入队栈转移过来（这会逆转顺序）。
class MyQueue:
def __init__(self):
self.push_stack = []
self.pop_stack = []
def push(self, x):
self.push_stack.append(x)
def pop(self):
if not self.pop_stack:
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
return self.pop_stack.pop()
def peek(self):
if not self.pop_stack:
while self.push_stack:
self.pop_stack.append(self.push_stack.pop())
return self.pop_stack[-1]
def empty(self):
return not self.push_stack and not self.pop_stack
- 均摊 \(O(1)\) 每次操作：每个元素最多在栈之间移动一次。
优先队列与堆¶
-
优先队列 总是返回最小（或最大）的元素，与插入顺序无关。标准实现是二叉堆。
-
最小堆 是一个完全二叉树，其中每个父节点都小于其子节点。最小值总是在根节点。以数组形式存储：节点 \(i\) 的子节点位于 \(2i + 1\) 和 \(2i + 2\) 位置。
| 操作 | 时间 |
|---|---|
| 插入 | \(O(\log n)\) |
| 获取最小值 | \(O(1)\) |
| 提取最小值 | \(O(\log n)\) |
| 从数组建堆 | \(O(n)\) |
- Python 的
heapq模块提供最小堆。要实现最大堆，可以将值取负。
import heapq
# 最小堆
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
print(heapq.heappop(h)) # 2（最小的）
# 最大堆技巧：取负值
heapq.heappush(h, -10)
print(-heapq.heappop(h)) # 10（最大的）
中等：数组中的第 K 个最大元素¶
-
问题：找出第 k 大的元素。
-
模式：维护一个大小为 \(k\) 的最小堆。堆的根就是第 k 大的元素。如果堆已有 \(k\) 个元素且新元素大于根，则替换根。
import heapq
def find_kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap) # O(k)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num) # 弹出最小，推入 num：O(log k)
return heap[0]
-
\(O(n \log k)\) 时间，\(O(k)\) 空间。当 \(k \ll n\) 时，远优于排序（\(O(n \log n)\)）。
-
陷阱：使用大小为 \(n\) 的最大堆然后弹出 \(k\) 次也有效但较慢：\(O(n + k \log n)\)。大小为 \(k\) 的最小堆是最优方法。
困难：合并 K 个有序链表¶
-
问题：合并 \(k\) 个已排序的链表为一个有序链表。
-
模式：使用一个最小堆，包含每个链表的头节点。弹出最小节点，加入结果，然后将其下一个节点推入堆。
import heapq
def merge_k_lists(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = ListNode(0)
curr = dummy
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
-
\(O(n \log k)\)，其中 \(n\) 是总节点数。堆中最多有 \(k\) 个元素。
-
陷阱：堆元组中的
i（索引）用于打破平局。没有它，当值相等时 Python 会尝试比较ListNode对象，而ListNode不支持<比较，会导致崩溃。索引确保了有效的比较。
常见陷阱总结¶
| 陷阱 | 示例 | 解决方法 |
|---|---|---|
fast.next 上的空指针 |
使用 while fast.next 检测环 |
检查 fast and fast.next |
| 未处理空链表 | 反转 None |
添加 if not head 守卫 |
| 栈下溢 | 从空栈弹出 | 检查 len(stack) > 0 或 if stack |
| 忘记哨兵 | 柱状图遗漏最后几个柱子 | 追加 0 来清空栈 |
| 堆中缺少打破平局的键 | 比较不可比较的对象 | 在堆元组中添加索引 |
| 遍历时修改链表 | 在遍历时删除节点 | 使用 prev/curr 模式或哑头 |
课后练习（NeetCode）¶
链表¶
- 反转链表 — 基础原地反转
- 合并两个有序链表 — 双指针合并
- 环形链表 — 快慢指针
- 重排链表 — 找中点 + 反转 + 合并
- 删除链表的倒数第 N 个节点 — 间隔为 \(n\) 的双指针
- LRU 缓存 — 哈希映射 + 双向链表
栈¶
堆 / 优先队列¶
- 数据流中的第 K 大元素 — 大小为 \(k\) 的最小堆
- 最后一块石头的重量 — 最大堆模拟
- 距离原点最近的 K 个点 — 按距离排序的最小堆
- 任务调度器 — 贪心 + 最大堆 + 冷却时间
- 数据流的中位数 — 两个堆（下半部分用最大堆，上半部分用最小堆）