链表、栈与队列¶

一句话总结：链表、栈、队列是构建复杂数据结构的三块基石，通过快慢指针、单调栈、堆等模式解决高频算法问题。

链表、栈与队列是更复杂数据结构的基石。本节先讲清它们的运作机制，然后一步步搭起关键模式——快慢指针、单调栈、基于堆的优先队列，配合由易到难的题目，每一步都点出常见坑。

数组能给你 \(O(1)\) 的随机访问，但插入代价昂贵。链表 (linked list) 给你快速插入，但没有随机访问。栈 (stack) 与队列 (queue) 限制你只能从一端或两端访问，正是这个限制让它们变得强大：限制你能做什么，反而简化了你要思考的东西。

链表¶

单链表 (singly linked list) 是一串节点链。每个节点存一个值和一个指向下一个节点的指针。最后一个节点指向 null。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

相对数组的优势：在已知位置插入或删除是 \(O(1)\) (只需重新指向指针)。无需移动元素。
劣势：访问第 \(i\) 个元素需要 \(O(i)\) 遍历 (没有随机访问)。缓存局部性差 (节点在内存中散落各处)。
双向链表 (doubly linked list) 多了一个 prev 指针，可以向后遍历。用于 LRU 缓存 (任意节点常数时间移除) 和浏览器历史 (前进/后退)。

操作	单向	双向
按索引访问	\(O(n)\)	\(O(n)\)
头部插入	\(O(1)\)	\(O(1)\)
尾部插入	\(O(n)\) 或 \(O(1)\)*	\(O(1)\)
删除给定节点	\(O(n)\)**	\(O(1)\)
查找	\(O(n)\)	\(O(n)\)

带尾指针时。*需要前驱节点，找前驱需要遍历。

哨兵节点 (sentinel nodes，dummy head/tail) 能简化边界情况。没有 dummy head 时，头部插入或头部删除都要写特殊分支。有了 dummy，每一个真实节点都有前驱。

# 无 dummy: 头部删除是特例
def delete_head(head):
    if not head:
        return None
    return head.next

# 有 dummy: 逻辑统一
dummy = ListNode(0)
dummy.next = head
# 现在每次删除都是: prev.next = prev.next.next

坑：忘记处理空链表 (head is None) 或单元素链表。永远测这些边界情况。

模式：快慢指针 (Floyd 算法)¶

用两个不同速度移动的指针来检测链表的性质。慢 (slow) 指针一次走一步；快 (fast) 指针一次走两步。

简单：链表是否有环¶

问题：判断链表是否有环。
模式：如果有环，快指针最终会追上慢指针 (相遇)。如果没有环，快指针会走到 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 (找环起点)¶

问题：返回环开始的节点。
模式：快慢指针相遇后，把其中一个指针重置回 head。两个指针都以速度 1 前进。它们会在环起点相遇。

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # 把一个指针重置回 head
            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，然后三个指针都向前走。顺序错了链表就废了。

栈¶

栈 (stack) 是 LIFO (Last In, First Out，后进先出)：最近加入的元素最先被移除。想象一摞盘子。
操作：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。"(((" 中间没有不匹配，但仍然不合法，因为还有开括号没闭合。

模式：单调栈¶

单调栈 (monotonic stack) 保持元素有序 (递增或递减)。当新元素会破坏这个顺序时，就一直弹出直到顺序恢复。
什么时候用：那种"对每个元素，找它左边/右边下一个更大/更小的元素"的题。整体是 \(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) 保证栈里剩下的柱子都会被处理。没有它，那些右边永远遇不到更矮柱子的柱子会被漏掉。

队列¶

队列 (queue) 是 FIFO (First In, First Out，先进先出)：元素从尾部加入、从头部移除。想象商店门口排队。
双端队列 (deque，double-ended queue) 支持两端 \(O(1)\) 的插入和删除。Python 的 collections.deque 是标准实现。
队列是广度优先搜索 (Breadth-First Search, BFS，见第 14 章第 4 节)、任务调度、消息传递 背后的结构。

简单：用栈实现队列¶

问题：只用两个栈实现队列。
模式：一个栈负责入，一个栈负责出。当出栈为空时，把入栈里的元素全部转移过来 (顺序自然被反转)。

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)\)：每个元素在两个栈之间最多被搬一次。

优先队列与堆¶

优先队列 (priority queue) 无视插入顺序，永远先返回最小 (或最大) 的元素。标准实现是二叉堆 (binary heap)。
最小堆 (min-heap) 是一棵完全二叉树，每个父节点都小于它的孩子。最小值永远在根。用数组存储：节点 \(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 模式或 dummy head

课后练习 (NeetCode)¶

链表¶

反转链表 — 最基本的原地反转
合并两个有序链表 — 双指针合并
链表环 — 快慢指针
重排链表 — 找中点 + 反转 + 合并
删除倒数第 N 个节点 — 间距为 \(n\) 的双指针
LRU 缓存 — 哈希表 + 双向链表

栈¶

有效的括号 — 括号配对
最小栈 — 每层追踪最小值
逆波兰表达式求值 — 基于栈的求值
每日温度 — 单调递减栈
柱状图中最大矩形 — 单调递增栈
车队 — 带到达时间的栈

堆 / 优先队列¶

数据流中第 K 大元素 — 大小为 \(k\) 的最小堆
最后一块石头的重量 — 最大堆模拟
距离原点最近的 K 个点 — 按距离的最小堆
任务调度器 — 最大堆 + 冷却期的贪心
数据流的中位数 — 双堆 (下半部最大堆、上半部最小堆)

📌 本节要点¶

链表 vs 数组：链表插入 \(O(1)\) 无随机访问，数组随机访问 \(O(1)\) 但插入贵。
哨兵节点：用 dummy head/tail 消除头尾特殊分支，让所有节点逻辑统一。
快慢指针：一慢一快同向前进，可检测环、找中点、定位环起点。
K 组反转：三指针 prev/curr/nxt 是原地反转的通用模板，必须背下来。
栈的三大用途：递归调用栈、表达式求值、撤销操作。
单调栈：维护单调顺序，适合"下一个更大/更小元素"类问题，均摊 \(O(n)\)。
两栈实现队列：一个入栈一个出栈，摊销 \(O(1)\)。
最小堆固定容量：求第 k 大用大小为 \(k\) 的最小堆，\(O(n \log k)\) 优于全排序。
堆元组打破平局：值相等时靠索引字段避免比较不可比对象导致的崩溃。
哨兵值清空栈：柱状图末尾追加 0，保证所有柱子都被处理。