罗罗编程学习记录
本页内容 展开查看

02.3.1.3 哑节点哨兵与合并排序

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.1 链表

02.3.1.3-001 合并两个有序链表(LC 21)怎么做?

一句话结论

哑节点 + 尾指针,双指针取较小节点接入结果链;一条走完接另一条剩余;O(m+n) 时间 O(1) 空间(复用节点)。

概念解释

  • 两链各自有序。
  • 尾指针维护结果链末尾。
  • 复用原节点,不新建值副本。

原理流程

  1. dummy 接结果链,tail=dummy。
  2. 两链非空取较小接入,指针后移。
  3. 剩余段直接接 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。
  • 堆顶为当前最小节点。
  • 取一个补一个。

原理流程

  1. 各链头节点入堆。
  2. 堆顶弹出接入结果。
  3. 后继非空入堆。
  4. 堆空结束。

代码 / 示例

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。

原理流程

  1. 区间内拆左右两半。
  2. 递归合并两半。
  3. 两结果再合并。

代码 / 示例

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) 空间;链表归并不需要额外数组。

概念解释

  • 切分:中点断链。
  • 递归:左右各自排序。
  • 合并:两有序段拼接。

原理流程

  1. 快慢找中点,断开。
  2. 递归排序左右。
  3. 合并两有序链。

代码 / 示例

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。
  • 断链:避免两段相连。

原理流程

  1. fast 起点决定偏左/偏右。
  2. 走到尾部取 slow。
  3. 断开并记录右段头。

代码 / 图示

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) 空间。

概念解释

  • 分区:按值大小分两链。
  • 稳定:原顺序保留。
  • 尾部互连。

原理流程

  1. 小、大两条哑链尾指针。
  2. 遍历按值接入对应链。
  3. 小链尾接大链头,大链尾置 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) 空间。

概念解释

  • 分组:每两节点一组。
  • 前驱:哑节点或上一组尾。
  • 组内交换。

原理流程

  1. dummy 接 head。
  2. 前驱 pre 指向待交换组。
  3. 存 a、b,改指针连接。
  4. 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 个一组。
  • 组内反转。
  • 组间连接:上组尾接下组新头。

原理流程

  1. 前驱定位,检查后续是否够 K 个。
  2. 组内反转,记录组尾与下一组头。
  3. 前驱接新头,组尾接下一组。

代码 / 示例

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) 空间;保留每组第一个。

概念解释

  • 有序:重复相邻。
  • 摘除后继:保留当前。
  • 前驱即当前节点。

原理流程

  1. cur 从 head 出发。
  2. cur.next 存在且同值则跳过。
  3. 否则 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 相反:重复组全部不要。
  • 前驱:待删组的前一节点。
  • 跳组:连续相同值全部摘除。

原理流程

  1. dummy 接 head,pre=dummy。
  2. 检查 pre.next 与 next.next。
  3. 同值记录值,跳过所有同值;否则 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 取模。
  • 成环便于找新尾。

原理流程

  1. 遍历求长度并成环。
  2. k %= n。
  3. 找新尾,断开,新头返回。

代码 / 示例

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…
  • 步骤:切半、反转、交替拼接。
  • 复用原节点。

原理流程

  1. 快慢找中点。
  2. 反转后半。
  3. 两链交替接入。

代码 / 示例

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;统一处理结果为空与首节点接入。

概念解释

  • 哑节点:结果链头不定。
  • 尾指针:避免每次找尾部。
  • 模板复用于合并、分区、构造。

原理流程

  1. 建 dummy 与 tail。
  2. 选节点接入 tail.next。
  3. tail 后移。
  4. 返回 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。
  • 归并各层保持稳定。

原理流程

  1. 比较相等时固定取一侧。
  2. 接入顺序与原序一致。
  3. 递归合并传递稳定性。

代码 / 图示

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) 时间。

概念解释

  • 数组:连续内存,合并需缓冲拷贝。
  • 链表:指针重连即可。
  • 递归栈两者都有。

原理流程

  1. 切分两段。
  2. 递归排序。
  3. 链表改指针合并,数组拷贝缓冲。

代码 / 图示

数组归并:临时数组 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 为堆高。

原理流程

  1. 初始 K 头入堆 O(K)。
  2. 每节点一次 poll/offer。
  3. 合计 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。

原理流程

  1. 拆分两段。
  2. 段尾断开处置 null。
  3. 拼接后确认尾节点。

代码 / 图示

分区:large.next = null
切半:slow.next = null
重排:前半尾置 null

常见误区

  • 误区:只断开前驱不置尾;正解:被分段尾节点仍可能挂旧后继。
  • 误区:拼接后忘清尾;正解:结果链尾部必须为 null。

追问

  • Q:怎么检查成环? A:快慢指针判环。
  • Q:尾节点残留何时暴露? A:遍历时重复访问同节点。

02.3.1.3-018 K 个一组反转的组间连接细节是什么?

一句话结论

组反转后原组首变组尾,新头为原组尾;上一组尾接新头,当前组尾作为下一组前驱;记录 nextGroup 防止反转后丢失后续。

概念解释

  • 反转前后首尾互换。
  • 前驱:上一组尾。
  • 后继:下一组头,反转前保存。

原理流程

  1. 保存下一组头。
  2. 组内反转。
  3. 前驱接新头,当前尾指向下一组。

代码 / 图示

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;验证哑节点、剩余段接入与堆判空。

概念解释

  • 空与最短:首节点处理。
  • 重复值:稳定性与去重口径。
  • 多链:空链不入堆。

原理流程

  1. 判空入口。
  2. 构造单链与一空一非空。
  3. 检查重复值与尾部。

代码 / 图示

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:链条数。
  • 空间:堆/栈/临时缓冲分列。

原理流程

  1. 统计总节点与链数。
  2. 标注每节点堆/合并代价。
  3. 辅助空间按结构说明。

代码 / 图示

两链合并: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),代价是实现更复杂。