Merge k Sorted Lists (Min-Heap)

用小根堆合并 k 个有序链表：每次弹出最小节点并推进。

#algorithm #snippet #evergreen #heap #linked-list #leetcode

[!info] related notes 算法面试题型 MOC 堆常见题

Merge k Sorted Lists (Min-Heap)

LeetCode: https://leetcode.cn/problems/merge-k-sorted-lists/

输入的每条链表按值非递减，并且无环、节点彼此不共享。此实现复用节点并重接 next，会改变输入链表的连接关系；若要求保留原链表，应构造结果副本。

思路

用小根堆（优先队列）按节点值排序。
先把每条链表的头节点入堆。
循环：弹出最小节点接到结果链表尾部；如果它有 next，把 next 入堆。

复杂度：

总节点数 N，链表数 k
时间：O(k + N log(max(k, 2)))，包括扫描所有输入头指针；堆中最多 k 个候选
空间：O(k)

Java Template

import java.util.*;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) {
            if (head != null) heap.add(head);
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            tail.next = cur;
            tail = cur;
            if (cur.next != null) heap.add(cur.next);
        }
        tail.next = null;
        return dummy.next;
    }
}

ListNode 由题目环境提供。比较器用 Integer.compare 避免整数相减溢出；相同值的跨链表顺序未保证稳定，但不影响值有序。共享尾节点不属于本例输入契约，否则同一对象可能重复入堆并破坏链接。

Merge k Sorted Lists (Min-Heap)

思路

Java Template

Related