02.3.1.3 哑节点哨兵与合并排序
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表
02.3.1.3-001 合并两个有序链表(LC 21)怎么做?
一句话结论
哑节点 + 尾指针,双指针取较小节点接入结果链;一条走完接另一条剩余;O(m+n) 时间 O(1) 空间(复用节点)。
概念解释
- 两链各自有序。
- 尾指针维护结果链末尾。
- 复用原节点,不新建值副本。
原理流程
- dummy 接结果链,tail=dummy。
- 两链非空取较小接入,指针后移。
- 剩余段直接接 tail。
代码 / 示例
public ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = a != null ? a : b;
return dummy.next;
}
常见误区
- 误区:忘记接剩余段;正解:一条走完另一条剩余整体接上。
- 误区:相等时取哪条影响稳定性;正解:先取 a 保持稳定。
追问
- Q:两链都空? A:dummy.next 为 null。
- Q:新建节点复制值? A:也可,但复用原节点省空间。
02.3.1.3-002 合并 K 个有序链表(LC 23)堆法怎么做?
一句话结论
小顶堆存 K 个链表当前头节点,每次取堆顶接入结果,该链下一节点入堆;O(N log K) 时间 O(K) 堆空间,N 为总节点数。
概念解释
- 堆规模 K。
- 堆顶为当前最小节点。
- 取一个补一个。
原理流程
- 各链头节点入堆。
- 堆顶弹出接入结果。
- 后继非空入堆。
- 堆空结束。
代码 / 示例
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> heap = new PriorityQueue<>((x, y) -> x.val - y.val);
for (ListNode h : lists) if (h != null) heap.offer(h);
ListNode dummy = new ListNode(0), tail = dummy;
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
tail.next = cur; tail = tail.next;
if (cur.next != null) heap.offer(cur.next);
}
return dummy.next;
}
常见误区
- 误区:空链入堆;正解:入堆前判空。
- 误区:堆按链表整体比较;正解:比较当前节点值。
追问
- Q:K=1 复杂度? A:直接返回该链 O(N)。
- Q:堆比较器相等怎么处理? A:相等顺序不影响结果正确性。
02.3.1.3-003 合并 K 个链表的分治做法是什么?
一句话结论
两两分治合并:相邻两链合并为一条,逐层归并;O(N log K) 时间 O(log K) 递归栈空间,避免堆的 K 规模依赖。
概念解释
- 分治:K 条分半递归。
- 合并:两链有序合并。
- 层数 log K。
原理流程
- 区间内拆左右两半。
- 递归合并两半。
- 两结果再合并。
代码 / 示例
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
ListNode merge(ListNode[] lists, int l, int r) {
if (l > r) return null;
if (l == r) return lists[l];
int m = (l + r) / 2;
return mergeTwo(merge(lists, l, m), merge(lists, m + 1, r));
}
常见误区
- 误区:分治是顺序两两合并;正解:树形归并,层数 log K。
- 误区:递归栈不计空间;正解:O(log K) 栈。
追问
- Q:堆法与分治法谁快? A:量级相同,堆法 O(K) 空间,分治 O(log K) 栈。
- Q:链表数组为空? A:返回 null。
02.3.1.3-004 排序链表(LC 148)归并怎么做?
一句话结论
快慢指针找中点切分,递归排序左右两段,再有序合并;O(n log n) 时间,递归栈 O(log n) 空间;链表归并不需要额外数组。
概念解释
- 切分:中点断链。
- 递归:左右各自排序。
- 合并:两有序段拼接。
原理流程
- 快慢找中点,断开。
- 递归排序左右。
- 合并两有序链。
代码 / 示例
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next; fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return mergeTwo(left, right);
}
常见误区
- 误区:找中点后不断链;正解:必须断开左右,否则递归成环。
- 误区:fast 初始 head 导致偶数长度偏右;正解:按口径选初始位置。
追问
- Q:链表快排可行吗? A:可行但随机分区与指针交换复杂,归并更常用。
- Q:空间 O(1) 排序? A:进阶有自底向上归并,消除递归栈。
02.3.1.3-005 链表归并怎么切分中点?
一句话结论
快慢指针定位中点,slow.next 作为右段头,断开 slow.next=null;偶数长度按实现口径偏左或偏右,切分后两段独立递归。
概念解释
- 切分点:slow。
- 右段:slow.next。
- 断链:避免两段相连。
原理流程
- fast 起点决定偏左/偏右。
- 走到尾部取 slow。
- 断开并记录右段头。
代码 / 图示
head → … → slow | mid → …
slow.next = null
左段 head…slow,右段 mid…
常见误区
- 误区:切分前未保存右段头;正解:先存 mid 再断链。
- 误区:单节点仍切分;正解:基准条件 head.next==null 直接返回。
追问
- Q:偶数长度偏左还是偏右? A:fast 初始 head.next 使 slow 偏左,按实现口径。
- Q:切分后左右长度差多少? A:最多差 1。
02.3.1.3-006 分隔链表(LC 86)怎么做?
一句话结论
两条哑链分别接小于 x 与大于等于 x 的节点,遍历完拼接;保持原相对顺序;O(n) 时间 O(1) 空间。
概念解释
- 分区:按值大小分两链。
- 稳定:原顺序保留。
- 尾部互连。
原理流程
- 小、大两条哑链尾指针。
- 遍历按值接入对应链。
- 小链尾接大链头,大链尾置 null。
代码 / 示例
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0), large = new ListNode(0);
ListNode s = small, l = large;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (cur.val < x) { s.next = cur; s = s.next; }
else { l.next = cur; l = l.next; }
}
l.next = null;
s.next = large.next;
return small.next;
}
常见误区
- 误区:大链尾未置 null;正解:可能残留旧链形成环。
- 误区:分区改变相对顺序;正解:尾插法保持稳定。
追问
- Q:等于 x 放哪侧? A:按题目口径,本例归 large。
- Q:空间 O(n) 做法? A:收集两批再拼接,不如原地指针。
02.3.1.3-007 两两交换链表节点(LC 24)怎么做?
一句话结论
哑节点出发,每两个一组交换前驱后继;指针顺序:先存后继组,改两条链接;O(n) 时间 O(1) 空间。
概念解释
- 分组:每两节点一组。
- 前驱:哑节点或上一组尾。
- 组内交换。
原理流程
- dummy 接 head。
- 前驱 pre 指向待交换组。
- 存 a、b,改指针连接。
- pre 移到组尾。
代码 / 示例
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode a = pre.next, b = a.next;
a.next = b.next;
b.next = a;
pre.next = b;
pre = a;
}
return dummy.next;
}
常见误区
- 误区:先改 a.next 丢 b.next;正解:先存 b 后继。
- 误区:奇数组未处理;正解:剩余单节点保留原位。
追问
- Q:递归版怎么写? A:交换前两节点,后继组递归返回新头接上。
- Q:组内节点值交换可以吗? A:可改值,但题目通常要求改指针。
02.3.1.3-008 K 个一组翻转链表(LC 25)怎么做?
一句话结论
先数够 K 个节点,不足则保留;组内按反转逻辑处理,组间首尾相接;哑节点记录上一组尾;O(n) 时间 O(1) 空间(递归版 O(K) 栈)。
概念解释
- 分组:每 K 个一组。
- 组内反转。
- 组间连接:上组尾接下组新头。
原理流程
- 前驱定位,检查后续是否够 K 个。
- 组内反转,记录组尾与下一组头。
- 前驱接新头,组尾接下一组。
代码 / 示例
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (true) {
ListNode tail = pre;
for (int i = 0; i < k && tail != null; i++) tail = tail.next;
if (tail == null) break;
ListNode start = pre.next, nextGroup = tail.next;
ListNode prev = nextGroup, cur = start;
while (cur != nextGroup) {
ListNode n = cur.next; cur.next = prev; prev = cur; cur = n;
}
pre.next = tail;
pre = start;
}
return dummy.next;
}
常见误区
- 误区:不足 K 个也反转;正解:末尾不足保留原序。
- 误区:组间连接错位;正解:组尾即原 start,接下一组头。
追问
- Q:K=1? A:链表不变。
- Q:递归思路? A:反转前 K 个,后继组递归返回新头拼接。
02.3.1.3-009 删除排序链表重复元素(LC 83)怎么做?
一句话结论
遍历链表,当前节点与 next 值相同则摘除 next;O(n) 时间 O(1) 空间;保留每组第一个。
概念解释
- 有序:重复相邻。
- 摘除后继:保留当前。
- 前驱即当前节点。
原理流程
- cur 从 head 出发。
- cur.next 存在且同值则跳过。
- 否则 cur 前进。
代码 / 示例
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
常见误区
- 误区:摘除后 cur 也前进;正解:继续检查新 next 是否仍重复。
- 误区:无序链表套用;正解:重复不相邻,需哈希。
追问
- Q:空链表? A:返回 null。
- Q:全部相同? A:保留首节点,其余摘除。
02.3.1.3-010 删除排序链表重复元素 II(LC 82)怎么做?
一句话结论
出现重复的节点整组删除;哑节点 + 前驱指针,检查后继两节点是否同值,同值则跳过整组;O(n) 时间 O(1) 空间。
概念解释
- 与 83 相反:重复组全部不要。
- 前驱:待删组的前一节点。
- 跳组:连续相同值全部摘除。
原理流程
- dummy 接 head,pre=dummy。
- 检查 pre.next 与 next.next。
- 同值记录值,跳过所有同值;否则 pre 前进。
代码 / 示例
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
if (pre.next.val == pre.next.next.val) {
int v = pre.next.val;
while (pre.next != null && pre.next.val == v) pre.next = pre.next.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
常见误区
- 误区:只删一个重复;正解:整组相同值都摘除。
- 误区:无前驱处理头节点重复;正解:哑节点统一前驱。
追问
- Q:保留哪个重复节点? A:本题全部删除,与 83 对照记忆。
- Q:重复组在尾部? A:跳过到 null 结束。
02.3.1.3-011 旋转链表(LC 61)怎么做?
一句话结论
先成环求长度,右移 k 取模,在新尾处断开;新尾为第 n-k 个节点,新头为其后继;O(n) 时间 O(1) 空间。
概念解释
- 右移:尾部节点移到头部。
- k 对 n 取模。
- 成环便于找新尾。
原理流程
- 遍历求长度并成环。
- k %= n。
- 找新尾,断开,新头返回。
代码 / 示例
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
int n = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; n++; }
k %= n;
if (k == 0) return head;
tail.next = head;
for (int i = 0; i < n - k; i++) tail = tail.next;
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
常见误区
- 误区:k 不取模;正解:k 可能大于 n。
- 误区:断开位置算错;正解:新尾走 n-k 步。
追问
- Q:k=0? A:原链返回。
- Q:左移 k 等价? A:右移 n-k。
02.3.1.3-012 链表重排(LC 143)怎么做?
一句话结论
快慢找中点,反转后半段,交替合并前半与后半;O(n) 时间 O(1) 空间。
概念解释
- 结构:L0→Ln→L1→Ln-1…
- 步骤:切半、反转、交替拼接。
- 复用原节点。
原理流程
- 快慢找中点。
- 反转后半。
- 两链交替接入。
代码 / 示例
public void reorderList(ListNode head) {
if (head == null) return;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next; fast = fast.next.next;
}
ListNode second = reverse(slow.next);
slow.next = null;
ListNode first = head;
while (second != null) {
ListNode f1 = first.next, s1 = second.next;
first.next = second; second.next = f1;
first = f1; second = s1;
}
}
ListNode reverse(ListNode h) {
ListNode prev = null;
while (h != null) { ListNode n = h.next; h.next = prev; prev = h; h = n; }
return prev;
}
常见误区
- 误区:交替拼接断链;正解:先存两侧后继再改指针。
- 误区:前半未断开;正解:slow.next 置 null。
追问
- Q:偶数长度后半口径? A:中点划分后后半不短于前半。
- Q:能否用栈存后半? A:可以但 O(n) 空间。
02.3.1.3-013 合并类题的哑节点模板是什么?
一句话结论
dummy.next=head,tail 指向结果链末尾;每接入一个节点 tail 后移;返回 dummy.next;统一处理结果为空与首节点接入。
概念解释
- 哑节点:结果链头不定。
- 尾指针:避免每次找尾部。
- 模板复用于合并、分区、构造。
原理流程
- 建 dummy 与 tail。
- 选节点接入 tail.next。
- tail 后移。
- 返回 dummy.next。
代码 / 示例
ListNode dummy = new ListNode(0), tail = dummy;
// tail.next = 选节点; tail = tail.next;
return dummy.next;
常见误区
- 误区:tail 初始为 null 再挂头;正解:dummy 消除首节点特判。
- 误区:接入后 tail 不前移;正解:尾部必须跟随最新节点。
追问
- Q:哑节点值要参与比较吗? A:不参与,仅哨兵。
- Q:结果链可能为空? A:dummy.next 为 null,口径统一。
02.3.1.3-014 有序链表合并为什么是稳定的?
一句话结论
相等节点先接入前一条链,保持原先后顺序;归并排序在链表上同样稳定;稳定要求相等时选择顺序明确。
概念解释
- 稳定:相等元素相对顺序不变。
- 合并选择:
<=先取 a。 - 归并各层保持稳定。
原理流程
- 比较相等时固定取一侧。
- 接入顺序与原序一致。
- 递归合并传递稳定性。
代码 / 图示
if (a.val <= b.val) { 先 a } else { 先 b }
常见误区
- 误区:相等时随意取;正解:稳定要求固定一侧。
- 误区:链表归并不稳定;正解:归并本身稳定。
追问
- Q:什么场景需要稳定? A:多关键字排序,次关键字顺序需保留。
- Q:链表排序不稳定会怎样? A:相等节点顺序可能颠倒。
02.3.1.3-015 链表归并与数组归并有什么不同?
一句话结论
数组归并需 O(n) 临时数组合并;链表归并只需改指针,合并段 O(1) 额外空间;两者都是 O(n log n) 时间。
概念解释
- 数组:连续内存,合并需缓冲拷贝。
- 链表:指针重连即可。
- 递归栈两者都有。
原理流程
- 切分两段。
- 递归排序。
- 链表改指针合并,数组拷贝缓冲。
代码 / 图示
数组归并:临时数组 O(n)
链表归并:指针重连 O(1) 额外
常见误区
- 误区:链表归并也要开临时节点数组;正解:复用原节点指针。
- 误区:链表归并空间 O(n);正解:辅助 O(1),递归栈 O(log n)。
追问
- Q:自底向上链表归并? A:消除递归栈,逐层按块合并。
- Q:链表排序为什么少用快排? A:随机访问差,分区指针操作复杂。
02.3.1.3-016 合并 K 链表的堆法复杂度怎么推?
一句话结论
N 个节点每个入堆、出堆各一次,堆大小 K,单次 O(log K);整体 O(N log K),堆空间 O(K)。
概念解释
- 堆规模 K:最多 K 个当前节点。
- 每节点一次堆操作。
- log K 为堆高。
原理流程
- 初始 K 头入堆 O(K)。
- 每节点一次 poll/offer。
- 合计 N·log K。
代码 / 图示
节点数 N,链数 K
堆操作:N 次 × O(log K)
空间:O(K)
常见误区
- 误区:堆大小 N;正解:只存各链当前头,规模 K。
- 误区:复杂度 O(N log N);正解:堆高 log K。
追问
- Q:K 接近 N? A:log K 接近 log N,退化为全排序量级。
- Q:堆法稳定性? A:相等节点顺序按堆实现,非严格稳定。
02.3.1.3-017 链表拆分时如何避免残留成环?
一句话结论
拆分/分区/重排后,最后一个节点的 next 必须置 null;否则旧链后继残留会形成环;所有断开操作都要收尾清尾指针。
概念解释
- 残留:节点仍指向旧后继。
- 成环:遍历不死。
- 收尾:尾指针置 null。
原理流程
- 拆分两段。
- 段尾断开处置 null。
- 拼接后确认尾节点。
代码 / 图示
分区:large.next = null
切半:slow.next = null
重排:前半尾置 null
常见误区
- 误区:只断开前驱不置尾;正解:被分段尾节点仍可能挂旧后继。
- 误区:拼接后忘清尾;正解:结果链尾部必须为 null。
追问
- Q:怎么检查成环? A:快慢指针判环。
- Q:尾节点残留何时暴露? A:遍历时重复访问同节点。
02.3.1.3-018 K 个一组反转的组间连接细节是什么?
一句话结论
组反转后原组首变组尾,新头为原组尾;上一组尾接新头,当前组尾作为下一组前驱;记录 nextGroup 防止反转后丢失后续。
概念解释
- 反转前后首尾互换。
- 前驱:上一组尾。
- 后继:下一组头,反转前保存。
原理流程
- 保存下一组头。
- 组内反转。
- 前驱接新头,当前尾指向下一组。
代码 / 图示
pre → [s1 s2 … sk] → nextGroup
反转后:pre → [sk … s1] → nextGroup
s1 成为新尾,pre = s1
常见误区
- 误区:反转后才找下一组头;正解:反转前保存 nextGroup。
- 误区:组间连接接反;正解:新头接前驱,旧首接后继。
追问
- Q:不足 K 个为什么不反转? A:题目要求末尾保留原序。
- Q:递归版组间连接? A:递归返回下组新头,当前组尾接上。
02.3.1.3-019 合并排序类题有哪些边界用例?
一句话结论
空链、单链、两链一空、完全重复值、逆序输入、K 含空链、K=1、节点数为 0;验证哑节点、剩余段接入与堆判空。
概念解释
- 空与最短:首节点处理。
- 重复值:稳定性与去重口径。
- 多链:空链不入堆。
原理流程
- 判空入口。
- 构造单链与一空一非空。
- 检查重复值与尾部。
代码 / 图示
null / 单节点
a 空 b 非空
全相同值
K 条含空
常见误区
- 误区:堆入堆未判空;正解:空链不进堆。
- 误区:合并剩余段遗漏;正解:循环结束接剩余。
追问
- Q:排序链表全相同? A:归并结果顺序保持,值不变。
- Q:K=0? A:返回 null,按题目口径。
02.3.1.3-020 合并排序类复杂度怎么汇报?
一句话结论
两链合并 O(m+n)/O(1);K 链堆法 O(N log K)/O(K),分治 O(N log K)/O(log K) 栈;链表排序归并 O(n log n)/O(log n) 栈(迭代版 O(1))。
概念解释
- N:总节点数。
- K:链条数。
- 空间:堆/栈/临时缓冲分列。
原理流程
- 统计总节点与链数。
- 标注每节点堆/合并代价。
- 辅助空间按结构说明。
代码 / 图示
两链合并:O(m+n) / O(1)
K 链堆法:O(N log K) / O(K)
链表归并:O(n log n) / O(log n) 栈
常见误区
- 误区:合并 K 链报 O(N log N);正解:堆高 log K。
- 误区:链表归并空间 O(n);正解:无临时数组,辅助 O(1),栈 O(log n)。
追问
- Q:分治递归栈最坏多少? A:平衡切分 O(log n)。
- Q:迭代归并空间? A:O(1),代价是实现更复杂。