合并 K 个升序链表

难度：⭐⭐⭐⭐ Hard

考点

• 分治法（归并思想）
• 最小堆（优先队列）
• 字节面试高频 Hard 题

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

函数签名

func mergeKLists(lists []*ListNode) *ListNode

示例

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

输入：lists = []
输出：nil

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

要求

1. 时间复杂度 O(N*logK)，N 为所有节点总数，K 为链表数量
2. 两种解法任选其一：分治归并 / 最小堆

提示

• 分治法：两两合并，不断归并 → 类似归并排序思想
• 堆方法：K 个链表头入堆，每次弹出最小的，再将其 next 入堆
• Go 实现堆需要实现 container/heap 的 Interface（Len, Less, Swap, Push, Pop）

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

type ListNode struct {
	Val  int
	Next *ListNode
}

// 分治法：两两归并
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	return divideAndConquer(lists, 0, len(lists)-1)
}

func divideAndConquer(lists []*ListNode, left, right int) *ListNode {
	if left == right {
		return lists[left]
	}
	mid := left + (right-left)/2
	l := divideAndConquer(lists, left, mid)
	r := divideAndConquer(lists, mid+1, right)
	return mergeTwoLists(l, r)
}

func mergeTwoLists(l1, 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
}