链表困难2 种解法

#23合并 K 个升序链表

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

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

解题主线

分治把 k 路归并拆成两两归并，使每个节点只参与约 log k 层合并。

最小堆始终保存每条未耗尽链表的当前头节点，弹出的节点就是全局最小候选。

设所有链表节点总数为 N；复杂度应按 N 与 k 表达，而不是只按某一条链表长度表达。

解法 1：分治归并

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

时间复杂度

O(N log k)，N 为全部节点数

空间复杂度

O(log k)，来自分治递归栈；合并过程复用原节点

23. 合并 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;
        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)，用于优先队列

23. 合并 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