链表困难2 种解法

#23合并 K 个升序链表

合并 k 个非递减链表，复用原节点并返回一个整体非递减的链表。

#链表#分治#优先队列#归并排序

原题

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

查看原题

解题主线

分治把 k 路归并拆成两两归并，使每个节点只参与约 log k 层合并。
最小堆始终保存每条未耗尽链表的当前头节点，弹出的节点就是全局最小候选。
设所有链表节点总数为 N；复杂度应按 N 与 k 表达，而不是只按某一条链表长度表达。

解法 1：分治归并

递归二分链表数组，先合并左右两半，再用双指针线性合并两条有序链表。

时间复杂度： O(N log k)，N 为全部节点数
空间复杂度： O(log k)，来自分治递归栈；合并过程复用原节点

JAVA

final class Solution {
    static final class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        // 分治区间最终归约为一条有序链表。
        return mergeRange(lists, 0, lists.length - 1);
    }

    private ListNode mergeRange(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        int middle = left + (right - left) / 2;
        // 左右区间先各自有序，再执行一次线性二路归并。
        ListNode first = mergeRange(lists, left, middle);
        ListNode second = mergeRange(lists, middle + 1, right);
        return mergeTwoLists(first, second);
    }

    private ListNode mergeTwoLists(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        // tail 之前始终是已确定的最小前缀，较小头节点可安全接入。
        while (first != null && second != null) {
            if (first.val <= second.val) {
                tail.next = first;
                first = first.next;
            } else {
                tail.next = second;
                second = second.next;
            }
            tail = tail.next;
        }
        tail.next = first != null ? first : second;
        return dummy.next;
    }
}

解法 2：最小堆多路归并

先把每条非空链表的头节点放入最小堆；每次取出最小节点接到答案尾部，并把它的后继补入堆。

时间复杂度： O(N log k)；堆中至多有 k 个节点
空间复杂度： O(k)，用于优先队列

JAVA

import java.util.Comparator;
import java.util.PriorityQueue;

final class Solution {
    static final class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> minimums = new PriorityQueue<>(
            Comparator.comparingInt(node -> node.val)
        );
        // 堆中每条未耗尽链表最多贡献一个当前头节点。
        for (ListNode head : lists) {
            if (head != null) minimums.offer(head);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        // 堆顶始终是所有剩余节点中的全局最小候选。
        while (!minimums.isEmpty()) {
            ListNode smallest = minimums.poll();
            // 弹出后只补入同一链表的后继，维持每路一个候选的不变量。
            if (smallest.next != null) minimums.offer(smallest.next);
            tail.next = smallest;
            tail = smallest;
        }
        return dummy.next;
    }
}

实现提示

去掉了旧文件中方向错误的大根堆变体，只保留正确的小根堆实现。

边界与易错点

旧 mergeKLists1 对比较器调用 reversed()，实际构造了大根堆，会按降序取节点；整理后明确使用小根堆。
比较器不要用 a.val - b.val，极端整数会溢出；Comparator.comparingInt 可安全比较。
两个解法都会重连输入节点；调用后不应再假设原链表结构保持不变。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/zhard/Q023_mergeKLists.java