链表、栈队列高频

• 三种方法的时间/空间复杂度
• 逐一合并 O(K²N) 与分治/堆 O(KN log K) 的差异
• 工程取舍（代码复杂度、稳定性、常数）

设链表总节点数 N、K 个链表。逐一合并：每次合并两个链表 O(N)，合并 K 次，但链会越来越长，总 O(K²·L)（L 为平均链长），若用 N 表示总节点则 O(KN)。分治合并：两两合并成对，再逐层合并，每层处理全部 N 个节点、共 log K 层，总 O(N log K)。小顶堆：把 K 个表头入堆，每次弹出最小后把其 next 入堆，共 N 次弹出、每次 O(log K)，总 O(N log K)，空间 O(K)。工程取舍：堆实现最直观且空间 O(K)、写起来短；分治无需额外堆空间（递归栈 O(log K)）且对"链表本身不可变"更友好；逐一合并简单但慢，仅当 K 很小用。三者都稳定（相等值按链表顺序）。

复杂度差异根源：逐一合并每轮都从 0 增长，导致 O(KN)；分治与堆都把"取最小"的代价降到 O(log K)。堆是"多路归并"的自然实现，分治是"二分归并"的推广。工程上堆最常用，分治在注重额外空间时更优。

• 快慢指针相遇判断有环
• 慢指针与快指针的步差（1 vs 2）为什么合适
• 相遇后重新找入环点的数学推导

判断有环：快指针每次走 2 步、慢指针每次走 1 步，若两者相遇则必有环。选步差 2 是因为：只要存在环，快指针相对慢指针以每步 1 个节点的速度逼近，必能在环内追上（且不会跳过，因为步差为 1 每次追近 1 格）。找入环点：设环前有 a 个节点、环长 b。首次相遇时，慢指针走了 a+s（s 为入环后走的距离），快指针走了 2(a+s)；又快指针比慢指针多走了 k 圈环，即 2(a+s)−(a+s)=a+s=kb，得 a+s=kb，即 a=kb−s。此时从相遇点出发走 a 步恰好（再绕 (k−1) 圈 + 环长−s）回到入环点。故把慢指针重置到头部，两指针都每次走 1 步，再次相遇点即入环点。步差通常取 2（1 步差更简单安全），步差过大可能跳过或需额外判断。

核心是"快慢指针的相对速度差为 1 格/步，保证环内必追上不成环则永不追"。入环点推导用同余思想：a ≡ −s (mod b)，即从相遇点再走 a 步与从头走 a 步在环内同位置。这也解释了为什么"慢指针重置头部、两指针同速"能定位入环点。

• 双栈结构：push 进 in、pop 从 out
• 转移（amortize）均摊 O(1)
• 为空判断与边界

用两个栈 in 与 out。push：直接压入 in 栈，O(1)。pop/peek：若 out 非空直接从 out 弹出；否则把 in 的所有元素逐个弹出压入 out（此时元素顺序反转，out 栈顶即队首），再从 out 弹出 O(1)。每个元素最多被压入 in 一次、弹出 in 一次、压入 out 一次、弹出 out 一次，共 4 次 O(1) 操作，因此均摊 O(1)。空判断：in 与 out 都为空才空。转移只在 out 为空时触发，且一旦转移，之后连续 pop 都 O(1)。

均摊 O(1) 的关键是"每个元素被转移进 out 恰好一次"，转移的总成本 O(n) 分摊到 n 个元素上，摊到每个操作 O(1)。这是"栈的 LIFO 反转为 FIFO"的经典技巧，利用了栈反转顺序的性质。

• 迭代反转的三指针（prev/cur/next）
• 递归反转的返回值与节点关系
• 成对交换维护前驱/后继

迭代反转：维护 prev 与 cur 与 next。循环内先保存 next=cur.next，再把 cur.next=prev，然后 prev=cur、cur=next。关键是先保存 next 再改指针，避免翻转后丢失后继。递归反转：reverse(head) 假设 head 之后已反转，head.next 成为新链尾，令 head.next.next=head、head.next=null，返回新头。成对交换：用哨兵 dummy 简化，维护 prev 与 first/second，先把 prev.next 指向 second，再 second.next=first、first.next=原 second.next，最后 prev=first。每步先保存后继再断链是避免断链的核心。

迭代三指针是"先存后改"范式；递归是"先递归后处理本节点"；成对交换本质是局部链反转，用哨兵统一空/单节点边界。三者共同点：任何指针改动前先保存即将被覆盖的后继，严格维护 prev/cur/next 的关系。

• 哈希表法 O(n) 空间 vs 插入-拆链 O(1) 空间
• 三步法：插入拷贝节点、映射 random、拆链
• 正确性：新节点紧邻原节点使 random 映射可计算

三步法：① 遍历原链表，在每节点后插入一个拷贝节点（值相同，即 new 节点作为原节点的 next）；② 再遍历，对每个原节点，其拷贝节点的 random 指向"原节点 random 的 next"（因为 random 指向的原节点后紧跟其拷贝节点）；③ 拆链：把拷贝节点逐个取出连成新链表，同时恢复原链表。空间 O(1)：不依赖哈希表，靠"拷贝节点紧邻原节点"这一几何关系建立映射。正确性：第二步中，原节点 p 的 random 指向 r，则 p 的拷贝 p' 的 random 应指向 r 的拷贝 r'，而 r' 正是 r.next，故 p.next.random = p.random.next。拆链保证原链表与新链表分离。

核心是"邻接拷贝"把哈希映射降到 O(1) 空间——新节点相对原节点位置固定，使随机指针的映射变成一次 next 寻址。相比哈希表法（O(n) 空间）更省空间，但需两遍遍历与拆链，稍复杂。这是"空间换时间"的反向优化。

• 单调队列维护"窗口内递减序列"
• 队首为当前窗口最大值，队尾淘汰更小元素
• 每个元素入队出队各一次，均摊 O(1)

维护一个双端队列，队首到队尾严格递减（存下标）。每次窗口右移：① 若队首下标已滑出窗口（<left）则弹出；② 新元素入队前，从队尾弹出所有小于等于它的元素（因为它们不可能再成为窗口最大值，且更早过期）；③ 队首即当前窗口最大值。为什么队尾淘汰更小元素安全：被淘汰的元素比新元素小且更早过期，任何时刻若新元素在窗口内，被淘汰者就永远不可能成为最大值。每个元素入队一次、出队一次，故均摊 O(1)，总 O(n)。

单调队列是"栈/队列 + 单调性"的经典应用，本质是维护一个"候选最大值"候选集：新元素淘汰掉所有比自己小且更早的，保证队列内单调递减。队首最大 + 队尾维护单调性，使每个元素操作 O(1)。这是滑动窗口最值问题的标准解法。

• 合并两个有序链表的哨兵技巧
• 链表归并排序：找中点+递归+合并
• 链表归并排序的空间复杂度 O(log n)（递归栈）

合并两个有序链表：用哨兵 dummy 与 cur 指针，比较两链表头，小者接入，某链耗尽后接另一链剩余。链表归并排序：递归地先找中点（快慢指针）拆成两半，递归排序两半，再合并。空间复杂度 O(log n)：虽然链表归并不需要像数组那样 O(n) 辅助数组，但递归需要 O(log n) 的调用栈。若用迭代自底向上归并，空间可到 O(1)。链表归并排序是稳定排序。

链表归并排序的空间优势来自"链表天然可 O(1) 拆分与合并"，无需 O(n) 辅助数组；代价是递归栈 O(log n)。合并两链表的哨兵技巧是基础，找中点用快慢指针避免先遍历求长度。相比数组归并 O(n) 空间，链表归并空间更优。

• 栈的 LIFO 匹配最近左括号
• 右括号判定：栈空或栈顶不匹配即非法
• 每类括号独立匹配

用栈：遍历字符串，遇到左括号（'('、'['、'{'）压栈；遇到右括号，弹出栈顶并检查是否匹配，若栈为空（无左括号可配）或栈顶与当前右括号不匹配则非法。正确性：括号嵌套时，最近未匹配的左括号在栈顶，与当前右括号匹配即为"最近配对"，栈的 LIFO 恰好模拟这一结构。三种括号混用时，只需保证弹出的栈顶与当前右括号类型相同（如 ')' 必须配 '('）。遍历结束若栈非空同样非法（有未闭合的左括号）。

括号匹配天然是"最近匹配"的嵌套结构，栈顶总是最近未匹配的左括号，这是 LIFO 与嵌套结构的对应。非法判定集中在右括号：栈空（无配对）或类型不符（错配）。最终栈空是完整闭合的必要条件。

• 辅助栈保存当前最小值历史
• 差值栈（存差值）优化空间
• pop 时同步恢复辅助栈/最小值

辅助栈法：数据栈存元素，辅助栈存"入栈时的当前最小值"。push 时辅助栈压入 min(当前值, 辅助栈顶)；pop 时两栈同时 pop，保证辅助栈顶始终是当前最小值；getMin 返回辅助栈顶。O(1) 时间、O(n) 空间。差值栈法：数据栈只存"当前值 − 当前最小值"的差值，另用一个变量 min 记录真正最小值。push(x)：若 x<min 则存 x−min 并更新 min=x，否则存 x−min；pop()：若栈顶差值为负，说明该元素是当时新最小值，恢复 min=min−top。getMin 返回 min。差值栈能省辅助栈空间，但需处理负值边界。

辅助栈是直观的"同步最小值历史"，其本质是"每个时刻的最小值都记录下来"。差值栈是"把最小值变化编码进差值"，用"栈顶为负表示该元素刷新了最小值"来恢复。pop 的同步维护是二者的共同难点：辅助栈要同步 pop，差值栈要按差值符号恢复 min。

• 哨兵 dummy 简化头部处理
• 每 K 个一组反转 + 连接
• 剩余不足 K 个不反转

用哨兵 dummy 指向头，维护 prev（已反转部分尾）与 cur（当前组起点）。每组处理：先检查剩余节点是否 ≥K，不足则跳出。反转组内 K 个节点（用 prev 后的节点逐个搬到 prev 之后完成反转），反转后 prev 移到组尾，cur 移到下一组起点。哨兵的作用：① 统一头部反转的边界（头部无需特判）；② 提供 prev 的初始位置，使第一组也能统一处理。最后返回 dummy.next。

哨兵 dummy 让"反转第一组"与"反转中间组"共用同一套逻辑，避免对空表/单节点/头部特判。题目核心是"每 K 个一组反转 + 剩余不足 K 不反转"，用"头插法"把 cur 后的节点逐个插入 prev 之后即可把 K 个节点顺序反转。

• 快慢指针找中点
• 反转后半段
• 逐对比较与恢复

O(1) 空间解法：① 快慢指针找中点（快指针走 2 步、慢走 1 步，快到头时慢在中点或中点前）；② 反转中点之后的后半段；③ 比较前半段与反转后的后半段是否逐节点相等；④ 恢复链表（可选，严谨起见再反转回去）。奇数长度时中点节点属于前半段，比较时跳过。空间 O(1)：只用了常数指针，相比"复制到数组"的 O(n) 空间更优。

三步法复用"找中点 + 反转链表"两个基础操作。反转后半段后，从两个头分别遍历即可判回文。O(1) 空间是相对"利用数组/栈存值"的优化，是链表情景下判回文的标准做法。

• 83：保留一个重复元素的指针推进
• 82：全部删除重复元素的哨兵与前驱
• 哨兵节点统一边界

83（保留一个）：cur 从 head 开始，若 cur.next 与 cur 值相同则 cur.next=cur.next.next（跳过重复），否则 cur=cur.next。只保留一个，无需哨兵。82（全部删除）：已排序，重复段整体删除。用哨兵 dummy 指向 head，维护 prev。cur=prev.next，若 cur.next 与 cur 值相同，则持续跳过直至不同，再 prev.next=跳过后的节点（删除整段）；若不同则 prev=cur。哨兵的作用：确保所有重复都能被删除，包括头部就是重复的情况（prev 指向 dummy 时也能删掉头部）。

83 是"去重保留一个"，用 cur 逐节点跳过；82 是"删除所有重复"，要保留前驱 prev 以删整段。哨兵对 82 尤其关键，因为头部重复时没有前驱，dummy 提供统一前驱。两者的指针推进差异体现了"保留 vs 全删"的语义。

• 递推式由 n-1 规模解推出 n 规模解
• O(n) 递推 vs O(nk) 链表模拟
• n 极大 k 小时用乘法跳步加速 O(k log n)

递推式：设 f(n,k) 为 n 人（编号 0..n-1）报数 k 时幸存者编号。第一轮报到 k 的人被移除，其编号为 (k−1) mod n。移除后，剩余 n−1 人重新从 k 报数，等价于把编号整体平移 k，即幸存者在新编号中的位置是 f(n−1,k)，映射回原编号为 f(n,k)=(f(n−1,k)+k) mod n。边界 f(1,k)=0。O(n) 递推：从 f(1)=0 迭代到 f(n)，每步 O(1)，总 O(n)。链表模拟：每轮删除要移动 O(k) 步，共 n−1 轮，总 O(nk)。加速：当 n 巨大而 k 很小时，若 k 远小于当前轮剩余人数 m，一次删一个太慢，可一次性跳过 ⌊(m−1)/k⌋ 轮（每轮删 1 人且周期 k 内不重复），用乘法定位，使每段 O(1)，总 O(k log n)（因每段人数按 k 倍缩减）。

递推式本质是"移除一人后，把剩余问题缩放为 n−1 规模并整体平移 k"。O(n) 递推是最常用解法；链表模拟直观但慢。跳跃加速的数学依据是"当剩余人数远大于 k 时，每轮删除位置都递增 k，可连续跳过多轮"，把常数次删除合并为一次定位，从而在 n 极大时显著加速。

• head/tail 取模回绕复用空间
• 空与满区分：显式 count 或空一格
• 2 的幂容量 + 按位与求模

数组 + head、tail 下标，tail 指向下一个写入位置。入队：arr[tail]=x，tail=(tail+1)%cap；出队：取 arr[head]，head=(head+1)%cap。取模回绕使空间循环复用。空与满：若只用 head==tail 判断，空（初始）与满（tail 追上 head）无法区分，故需显式 count 计数（或空一格，即最多存 cap−1 个，满时 (tail+1)%cap==head）。用 count 最直观：count==0 空、count==cap 满。2 的幂容量：当 cap 是 2 的幂，tail=(tail+1)&(cap−1)（按位与）等价于取模，且 & 比 % 快得多，利于性能敏感场景（如 Ring Buffer）。

循环队列的核心是"取模回绕"实现空间复用，难点是空满判定——head==tail 二义性，需 count 或空一格消歧。2 的幂容量 + 按位与是工程优化，把昂贵的取模运算换成位运算。这是无锁队列、环形缓冲（如 Kafka、日志）的底层结构。

• 栈模拟：操作数入栈、遇运算符弹出两数
• 操作数顺序（先弹出的是右操作数）
• 除法向零截断

栈模拟：遍历 token，数字压栈；遇运算符弹出两个操作数 b（先弹出）与 a（后弹出），按 a OP b 计算后压栈。关键是顺序：栈是 LIFO，先弹出的是后入栈的右操作数 b，后弹出的是左操作数 a，对于减法/除法必须 a−b 与 a/b 保证正确。除法：LeetCode 要求向零截断（truncate toward zero），对非负除法与整数除法一致，对负数如 −7/2 应得 −3（向零，而非向下取整 −4）。Java 中 int 除法本身就是向零截断，故直接用 a/b 即可。

逆波兰表达式是后缀表达式，天然无括号，栈是标准求值器。核心易错点是操作数顺序：栈顶是右操作数。除法截断方向取决于题目要求（多数为向零截断），Java 的 int 除法天然满足，但需注意语言差异（有的语言向负无穷）。

• 队列实现栈：每次 pop 需把前 n-1 个倒腾到另一队列
• 栈实现队列：双栈分摊 O(1)
• 两者数据结构特性差异

用队列实现栈：pop/top 时需把除队尾外的 n−1 个元素移到另一队列，再把队尾返回，故 pop 为 O(n)（每次倒腾必然发生）。用栈实现队列：push 进 in，pop 时若 out 空则把 in 全部倒到 out，之后连续 pop 都 O(1)，均摊 O(1)。差异根源：队列是 FIFO，要取队尾（栈顶）必须把前面所有元素倒腾走，无法像栈反转那样"一次倒腾长期受益"；而双栈把一次倒腾的 O(n) 摊到 n 个元素上，故均摊 O(1)。简言之，队列→栈"倒腾"无法摊销（每次都得倒），栈→队列"倒腾"可摊销（倒一次管多次）。

关键区别是"反转的持久性"：把 in 倒入 out 后，out 顶部就是队列头，之后多次 pop 都受益，故倒腾成本可摊还；而队列倒腾后，新加入的队列尾仍压在下方，下次 pop 又得倒腾，无法摊销。这解释了为什么一个 O(n) 一个均摊 O(1)。

• 双指针交替遍历两条链
• 消除长度差：指针走完一条后走另一条
• 无交点时两指针同时为 null

双指针 pA、pB 分别从 A、B 头出发。每步都前进，若 pA 走到末尾则跳到 B 头，pB 走到末尾则跳到 A 头。这样两个指针在任何时刻走过的"步数"始终相同，抵消长度差——它们会在交点处相遇（因为有交点时，总共走了相同步数后到达同一节点）。无交点时：两指针在各自走完两条链后同时到达 null（都走了 a+b 步），此时 pA==pB==null，循环终止，返回 null。正确性：两指针总步数一致，相遇点即交点；无交点则同时到 null。

该技巧的核心是"让两个指针走过相同的总步长"，从而消除两条链长度差。有交点时：pA 走 a+c 后若未遇则走 b，pB 走 b+c 后走 a，二者在交点处步数相同。无交点时都走完 a+b 步同时为 null，优雅终止。

• 三步法：找中点、反转后半段、穿插合并
• 每步的正确性依赖
• 边界处理（奇偶长度）

重排链表（L0→Ln→L1→Ln-1→...）：① 快慢指针找中点，把链表分成前半段与后半段；② 反转后半段；③ 把反转后的后半段穿插合并进前半段（每次取前半段头与后半段头交替连接）。每步依赖上一步：穿插合并依赖"后半段已反转"（否则顺序不对）；反转依赖"中点找得对"（否则反转错段）；找中点依赖快慢指针正确终止。奇数长度时中点归属前半段，穿插时后半段更短，需处理后半段先耗尽的情况。总 O(n) 时间、O(1) 空间。

该题是"找中点 + 反转 + 合并"三个基础技巧的组合，是链表的综合题。穿插合并是核心：用两指针分别指向两段头，交替取下一节点，连接成要求的交错序。每步正确性环环相扣，凸显"分步验证"的工程思维。

• 快慢指针：快指针先走 N 步
• 哨兵节点处理删除头结点
• 一次遍历 O(n)

用哨兵 dummy 指向 head，快指针 fast 先走 N 步，然后快慢指针 slow 一起前进，直到 fast 到达末尾。此时 slow 指向"待删节点的前驱"（因为 fast 领先 slow 恰好 N 步），执行 slow.next=slow.next.next 删除。哨兵 dummy 的作用：当待删节点是头结点时，slow 初始为 dummy，保证删除头结点也能统一处理（否则无法删除头结点）。快指针先走 N 步而非 N+1，配合哨兵使 slow 恰好停在待删节点的前驱。一次遍历 O(n)。

双指针法是"一次遍历"的关键：fast 先走 N 步建立 N 的间距，再同步前进到末尾，slow 自然落在倒数第 N+1 个节点（待删前驱）。哨兵解决"删头"边界。相比"先求长度再定位"的两次遍历，这是更优解法。

• 快指针走 2 步、慢指针走 1 步
• 奇数长度慢指针在中点，偶数长度在中点靠前
• 终止条件 fast==null/fast.next==null

快慢指针：fast 每次走 2 步，slow 每次走 1 步。fast 到达末尾时 slow 恰好在中点。终止条件：① fast==null（偶数长度，fast 走完正好跳出）；② fast.next==null（奇数长度，fast 到最后一个节点）。奇数长度时 slow 指向正中间节点；偶数长度时 slow 指向两个中间节点的前者（靠前中点）。"安全"在于：快指针每步都检查 fast≠null 且 fast.next≠null 再前进，不会出现空指针；且 slow 永远中庸，不会越界。

快慢指针是"找中点"的标准技巧，两个终止条件分别对应奇偶长度。理解"偶数时 slow 靠前、奇数时 slow 正中"对后续操作（如反转后半段、分成两段）至关重要。终止条件的选择取决于是否需要偏前或偏后的中点。

• 多级双向链表结构（child 指针）
• 栈模拟 DFS 扁平化顺序
• 正确重连 next/prev 与清除 child

用栈模拟 DFS：迭代遍历，遇到有 child 的节点时，先把其 next（若有）压栈，再转向 child 继续；无 child 时沿 next 前进，若 next 为空则从栈弹出最近保存的 next 继续。扁平化重连：当节点有 child 时，把 child 设为 next，child.prev 指向当前节点，当前节点的 child 置 null；child 链的末尾的 next 指向栈弹出的节点并设置其 prev。栈保证了"先探 child 子树，再回到原 next"的 DFS 顺序。正确重连的关键：① 每个连接都要同时维护 next 与 prev 双向；② 用完的 child 要置 null 不再保留。

多级链表可视为"树"，扁平化即"按 DFS 序重排为单链表"。栈保存"旁路 next"以支持回溯。重连难点是双向一致性：设置 next 时同步设置反向的 prev，且 child 链尾与旁路 next 正确衔接。用栈比递归的显式好处是避免深递归栈溢出。