LeetCode LCR 078. 合并 K 个升序链表

Categories:

题目描述
思路分析
1. 解法一：最小堆（优先队列）（推荐）
2. 解法二：分治归并
相似题目

题目描述

✅ LCR 078. 合并 K 个升序链表

思路分析

解法一：最小堆（优先队列）（推荐）

核心思路：

k 个链表的当前最小值必然在各链表头节点中产生，用最小堆维护”候选集”：

将所有非空链表头节点入堆（堆大小为 k）

每次弹出堆顶（全局最小），接到结果链表

将弹出节点的后继节点（若非空）重新入堆

堆为空时结束

堆的大小始终 ≤ k，每次操作 O(log k)，总节点数 N 次操作 → O(N log k)。

复杂度分析：

时间复杂度：O(N log k)，其中 N 为总节点数，k 为链表数

空间复杂度：O(k)，堆的大小始终不超过 k

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );
        // 将所有链表头节点入堆
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!minHeap.isEmpty()) {
            ListNode node = minHeap.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) {
                minHeap.offer(node.next); // 将后继节点补入堆
            }
        }
        return dummy.next;
    }
}

type ListHeap []*ListNode

func (h ListHeap) Len() int            { return len(h) }
func (h ListHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h ListHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *ListHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *ListHeap) Pop() interface{} {
	old := *h
	n := len(old)
	node := old[n-1]
	*h = old[:n-1]
	return node
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &ListHeap{}
	heap.Init(h)

	// 将所有链表头节点入堆
	for _, node := range lists {
		if node != nil {
			heap.Push(h, node)
		}
	}

	dummy := &ListNode{}
	cur := dummy
	for h.Len() > 0 {
		node := heap.Pop(h).(*ListNode)
		cur.Next = node
		cur = cur.Next
		if node.Next != nil {
			heap.Push(h, node.Next) // 将后继节点补入堆
		}
	}
	return dummy.Next
}

解法二：分治归并

核心思路：

类比归并排序，将 k 条链表两两配对合并，一轮后缩减为 k/2 条；反复合并共 log k 轮，每轮总工作量 O(N)。

比顺序合并快的原因：分治使每次合并两段长度均衡，避免顺序合并后期链表越来越长导致每次合并代价递增的问题。

复杂度分析：

时间复杂度：O(N log k)，其中 N 为总节点数，k 为链表数

空间复杂度：O(log k)，递归栈深度

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	// 分治：将链表数组对半拆分，分别合并
	mid := len(lists) / 2
	l1 := mergeKLists(lists[:mid])
	l2 := mergeKLists(lists[mid:])
	return mergeTwoLists(l1, l2)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	cur := dummy
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			cur.Next = l1
			l1 = l1.Next
		} else {
			cur.Next = l2
			l2 = l2.Next
		}
		cur = cur.Next
	}
	if l1 != nil {
		cur.Next = l1
	} else {
		cur.Next = l2
	}
	return dummy.Next
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	链表、双指针
148. 排序链表	中等	链表、归并排序
264. 丑数 II	中等	堆、动态规划
355. 设计推特	中等	堆、链表
373. 查找和最小的 K 对数字	中等	堆
378. 有序矩阵中第 K 小的元素	中等	堆、二分
632. 最小区间	困难	堆、滑动窗口
786. 第 K 个最小的素数分数	中等	堆
1439. 有序矩阵中的第 k 个最小数组和	困难	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/67254571