Linked Lists, Stacks, and Queues¶

linked list、stack 和 queue 是更复杂数据结构的基础构件。本文件先讲清它们的工作机制，再通过逐步升级的问题介绍关键模式：快慢指针、monotonic stack 与基于 heap 的 priority queue，并总结每一步常见陷阱。

array 提供快速随机访问，但插入代价高。linked list 提供快速插入，但不支持随机访问。stack 与 queue 通过限制访问位置（一个端点或两个端点）获得了强大的问题建模能力：可操作性越受限，思考路径往往越清晰。

Linked List¶

singly linked list 是由 node 串成的链。每个 node 存一个值和指向下一个 node 的指针。最后一个 node 指向 null。

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

相对 array 的优势：在已知位置插入/删除是 \(O(1)\)（只需改指针），不需要搬移元素。
劣势：访问第 \(i\) 个元素需要 \(O(i)\) 遍历（没有随机访问）；缓存局部性差（node 在内存中不连续）。
doubly linked list 增加 prev 指针，可向后遍历。常用于 LRU cache（可 \(O(1)\) 删除任意 node）和浏览器历史（前进/后退）。

Operation	Singly	Doubly
Access by index	\(O(n)\)	\(O(n)\)
Insert at head	\(O(1)\)	\(O(1)\)
Insert at tail	\(O(n)\) or \(O(1)\)*	\(O(1)\)
Delete given node	\(O(n)\)**	\(O(1)\)
Search	\(O(n)\)	\(O(n)\)

有 tail 指针时可 \(O(1)\)。*需先找前驱，通常要遍历。

sentinel node（dummy head/tail）可显著简化边界情况。若没有 dummy head，插入/删除头节点通常需要单独分支；有 dummy 后，每个真实 node 都有前驱，逻辑可统一。

# Without dummy: special case for head deletion
def delete_head(head):
    if not head:
        return None
    return head.next

# With dummy: uniform logic
dummy = ListNode(0)
dummy.next = head
# now every deletion is: prev.next = prev.next.next

常见坑：忘记处理空链表（head is None）或单节点链表。务必单测这些边界输入。

Pattern: Fast and Slow Pointer（Floyd）¶

使用两个不同速度的指针来检测 linked list 性质。slow 每次走一步，fast 每次走两步。

Easy: Linked List Cycle¶

问题：判断 linked list 是否有 cycle。
模式：如果有 cycle，fast 最终会“追上” slow（两者相遇）；如果无 cycle，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

为什么正确：若 cycle 长度为 \(c\)，fast 每轮相对 slow 追近 1 个 node，slow 进入 cycle 后最多 \(c\) 步必相遇。
常见坑：循环条件应是 fast and fast.next，不能只写 fast.next。因为 fast 可能先成为 None。

Medium: Find the Middle of a Linked List¶

问题：返回中间 node。
模式：当 fast 到达尾部时，slow 正好在中间。

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at the middle (or second middle if even length)

Medium: Linked List Cycle II（Find Cycle Start）¶

问题：返回 cycle 起点 node。
模式：fast 与 slow 首次相遇后，把一根指针重置到 head。两者都改为一步一走，再次相遇点即 cycle 起点。

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # reset one pointer to head
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

为什么正确：设 head 到 cycle 起点距离为 \(a\)，起点到首次相遇点距离为 \(b\)。则 slow 走了 \(a+b\)，fast 走了 \(2(a+b)\)，差值为整圈长度 \(c\)，所以 \(a+b=c\)，即 \(a=c-b\)。因此“head 到起点”与“相遇点沿环到起点”距离相同。

Hard: Reverse Linked List in Groups of K¶

问题：每 \(k\) 个 node 为一组翻转。

def reverse_k_group(head, k):
    # check if we have k nodes left
    node = head
    for _ in range(k):
        if not node:
            return head
        node = node.next

    # reverse k nodes
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # head is now the tail of the reversed group
    # recursively process the rest
    head.next = reverse_k_group(curr, k)
    return prev  # prev is the new head of this group

常见坑：原地翻转模板（prev, curr, nxt）建议牢牢记住。每步都要先把 curr.next 指回 prev，再整体推进三个指针；顺序错了会破坏链表。

Stack¶

stack 是 LIFO（Last In, First Out）：最后入栈的元素最先出栈，可类比盘子堆。
常用操作：push(x) 入栈、pop() 出栈、peek() 查看栈顶不弹出，均为 \(O(1)\)。
stack 是许多机制的隐式基础：递归（call stack）、表达式求值（中缀转后缀）、撤销操作（undo）。

Easy: Valid Parentheses¶

问题：给定括号串 ()[]{}，判断是否平衡。
模式：左括号入栈；遇到右括号时检查栈顶是否匹配。

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。如字符串 "(((" 中途不会失配，但仍不合法。

Pattern: Monotonic Stack¶

monotonic stack 始终维持元素单调（递增或递减）。当新元素破坏单调性时，持续 pop 直到恢复单调。
适用场景：题目常问“对每个元素，找下一个/上一个更大/更小元素”。该模式整体是 \(O(n)\)，因为每个元素最多 push 一次、pop 一次。

Medium: Daily Temperatures¶

问题：给定每日温度，求每一天还要等几天才会出现更高温度。
模式：栈里存索引。当前温度高于栈顶对应温度时，持续弹栈并记录距离。

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # stack of indices, temperatures in decreasing order

    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)\)。
常见坑：栈里应存索引而非温度值，因为你最终需要计算天数差。

Hard: Largest Rectangle in Histogram¶

问题：给定柱状图高度数组，求最大矩形面积。
模式：对每根柱子，找其能向左/向右扩展到哪里（即两侧最近更矮柱子）。使用单调递增栈可高效完成。

def largest_rectangle(heights):
    stack = []  # stack of indices, heights in increasing order
    max_area = 0
    heights.append(0)  # sentinel to flush the stack at the end

    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  # this bar can extend back to where the popped bar started
        stack.append((start, h))

    heights.pop()  # remove sentinel
    return max_area

常见坑：start = idx 这一行很容易漏。弹出更高柱后，当前较矮柱可向左扩展到被弹柱的起点；漏掉会导致面积计算错误。
常见坑：heights.append(0) 这个 sentinel 用来强制清空剩余栈元素。没有它，右侧始终没遇到更矮柱的条形会被漏算。

Queue¶

queue 是 FIFO（First In, First Out）：从尾部入队、从头部出队，可类比排队。
deque（double-ended queue）支持两端 \(O(1)\) 插入与删除。Python 推荐使用 collections.deque。
queue 是 BFS（第 14 章文件 4）、任务调度、消息传递等模式的核心结构。

Easy: Implement Queue Using Stacks¶

问题：只用两个 stack 实现 queue。
模式：一个 stack 负责 push，一个 stack 负责 pop。pop 栈为空时，把 push 栈元素全部倒入（顺序翻转）。

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

Priority Queue 与 Heap¶

priority queue 不按插入顺序，而是优先返回最小（或最大）元素。标准实现是 binary heap。
min-heap 是完全二叉树，满足每个父节点都不大于子节点；最小值总在根。常以数组存储：下标 \(i\) 的子节点下标是 \(2i+1\) 与 \(2i+2\)。

Operation	Time
Insert	\(O(\log n)\)
Get min	\(O(1)\)
Extract min	\(O(\log n)\)
Build heap from array	\(O(n)\)

Python 的 heapq 默认是 min-heap；若要 max-heap，可对值取反。

import heapq

# Min-heap
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
print(heapq.heappop(h))  # 2 (smallest)

# Max-heap trick: negate values
heapq.heappush(h, -10)
print(-heapq.heappop(h))  # 10 (largest)

Medium: Kth Largest Element in an Array¶

问题：找数组中第 \(k\) 大元素。
模式：维护一个大小为 \(k\) 的 min-heap。堆顶就是第 \(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)  # pop min, push num: O(log k)

    return heap[0]

时间 \(O(n \log k)\)，空间 \(O(k)\)。当 \(k \ll n\) 时，比完整排序 \(O(n \log n)\) 更优。
常见坑：也可以用大小为 \(n\) 的 max-heap 再弹 \(k\) 次，但更慢：\(O(n + k \log n)\)。固定大小为 \(k\) 的 min-heap 才是更优策略。

Hard: Merge K Sorted Lists¶

问题：将 \(k\) 个有序 linked list 合并成一个有序链表。
模式：min-heap 初始放每条链表的头节点。每次弹最小 node 接到结果链表，再把该 node 的下一个入堆。

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（列表索引）是 tiebreaker。若省略它，当值相等时 Python 会尝试比较 ListNode 对象并报错（ListNode 不支持 <）。

Common Pitfalls Summary¶

Pitfall	Example	Fix
`fast.next` 空指针	Cycle detection 里写成 `while fast.next`	用 `fast and fast.next`
未处理空链表	对 `None` 做 reverse	先加 `if not head`
stack 下溢	空栈直接 pop	先判断 `if stack`
忘记 sentinel	histogram 漏算末尾柱子	末尾追加 0 强制清栈
heap 无 tiebreaker	值相等时比较不可比较对象	堆元组加入索引
遍历时改链表	一边走一边删导致断链	使用 prev/curr 模式或 dummy head

Take-Home Problems（NeetCode）¶

Linked List¶

Reverse Linked List — 最基础的原地翻转
Merge Two Sorted Lists — 双指针合并
Linked List Cycle — 快慢指针
Reorder List — 找中点 + 翻转 + 合并
Remove Nth Node From End — 双指针间隔 \(n\)
LRU Cache — hash map + doubly linked list

Stack¶

Valid Parentheses — 括号匹配
Min Stack — 栈内同步维护最小值
Evaluate Reverse Polish Notation — stack 表达式求值
Daily Temperatures — 单调递减栈
Largest Rectangle in Histogram — 单调递增栈
Car Fleet — 基于到达时间的 stack

Heap / Priority Queue¶

Kth Largest Element in a Stream — 固定大小 \(k\) 的 min-heap
Last Stone Weight — max-heap 模拟
K Closest Points to Origin — 按距离建 heap
Task Scheduler — max-heap + 冷却队列
Find Median from Data Stream — 双 heap（小顶堆 + 大顶堆）