链表、栈与队列

链表、栈与队列

链表、栈和队列是构建更复杂数据结构的基石。本文件先讲清它们的工作机制，再通过难度递增的题目构建出关键模式：快慢指针、单调栈以及基于堆的优先队列，并在每一步指出常见陷阱。

• 数组给你快速的随机访问，但插入很贵。链表给你快速插入，但没有随机访问。栈和队列把访问限制在一端或两端，而正是这种限制赋予了它们力量：通过约束你能做什么，简化了你需要操心的事情。

链表

• **单链表（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(1) 删除任意节点）和浏览器历史（前进/后退）。

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

• **哨兵节点（sentinel node，哑节点 dummy head/tail）**能简化边界情况。没有哑头的话，在头部插入或删除头部需要特判代码。有了哑头，每个真实节点都有前驱。

# 没有哑节点：删头部要特判
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（后进先出，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 是标准实现。

• 队列是 BFS（广度优先搜索，见文件 04）、任务调度和消息传递背后的结构。

简单：用栈实现队列

• 题目：只用两个栈来实现一个队列。

• 模式：一个栈用来压入，一个用来弹出。当弹栈为空时，把压栈里的所有元素倒过去（顺序反转）。

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。

• 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 不支持 <，会崩溃。下标保证了比较合法。

常见陷阱汇总

编程练习（使用 CoLab 或 notebook）

以下题目可在 NeetCode 的题目列表中练习。

链表

• Reverse Linked List（反转链表）—— 基础的原地反转
• Merge Two Sorted Lists（合并两个有序链表）—— 双指针归并
• Linked List Cycle（环形链表）—— 快慢指针
• Reorder List（重排链表）—— 找中点 + 反转 + 合并
• Remove Nth Node From End（删除倒数第 N 个节点）—— 间隔 n 的双指针
• LRU Cache（LRU 缓存）—— 哈希表 + 双链表

栈

• Valid Parentheses（有效的括号）—— 括号匹配
• Min Stack（最小栈）—— 每一层都追踪最小值
• Evaluate Reverse Polish Notation（逆波兰表达式求值）—— 基于栈的求值
• Daily Temperatures（每日温度）—— 单调递减栈
• Largest Rectangle in Histogram（柱状图中最大的矩形）—— 单调递增栈
• Car Fleet（车队）—— 用到达目标的时间构造栈

堆 / 优先队列

• Kth Largest Element in a Stream（数据流中第 K 大元素）—— 大小为 k 的最小堆
• Last Stone Weight（最后一块石头的重量）—— 最大堆模拟
• K Closest Points to Origin（K 个距离原点最近的点）—— 按距离的最小堆
• Task Scheduler（任务调度器）—— 贪心 + 最大堆 + 冷却
• Find Median from Data Stream（数据流的中位数）—— 双堆（下半部分最大堆，上半部分最小堆）