【华为机试】23. 合并 K 个升序链表

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

解题思路

算法分析

这道题是链表合并和分治算法的经典应用。主要解法包括：

1. 逐一合并法：依次合并两个链表，简单但效率低
2. 分治合并法：类似归并排序，递归分治合并
3. 优先队列法：使用最小堆维护各链表头节点
4. 数组排序法：收集所有节点后排序重建链表

问题本质分析

分治算法详解

两个链表合并过程

分治树结构

优先队列解法

各种解法对比

算法流程图

代码实现思路

1. 链表节点定义：

   • 标准单链表节点结构
   • 包含值和下一个节点指针

2. 分治合并实现：

   • 递归分割链表数组
   • 合并两个有序链表的经典算法
   • 时间复杂度最优

3. 优先队列实现：

   • 使用堆维护所有链表的当前最小节点
   • 每次取出最小节点并添加其后继
   • 适合K很大的情况

4. 边界处理：

   • 空数组、单链表、空链表的处理
   • 链表长度不等的情况

时间复杂度分析

• 逐一合并法：O_kn，k为链表数量，n为总节点数
• 分治合并法：O_nlogk，最优解法
• 优先队列法：O_nlogk，稳定高效
• 数组排序法：O_nlogn，简单但空间消耗大

空间复杂度分析

• 逐一合并法：O常数，原地操作
• 分治合并法：O_logk，递归栈深度
• 优先队列法：O_k，堆存储空间
• 数组排序法：O_n，额外数组空间

关键优化点

1. 分治策略：将O_kn优化为O_nlogk
2. 虚拟头节点：简化链表合并逻辑
3. 递归优化：合理的递归边界处理
4. 内存管理：复用原有节点，避免额外分配

边界情况处理

1. 空数组：直接返回null
2. 单个链表：直接返回该链表
3. 包含空链表：跳过空链表处理
4. 所有链表为空：返回null

实际应用场景

1. 外部排序：合并多个已排序的文件
2. 分布式系统：合并多个节点的排序结果
3. 数据库：多路归并排序的实现
4. 搜索引擎：合并多个索引的结果

算法扩展

性能优化技巧

测试用例设计

这个问题的关键在于理解分治算法的优势和掌握链表合并的基本操作，通过递归分治将复杂的多路归并问题转化为简单的两路归并问题。

完整题解代码

package mainimport ("container/heap""fmt""sort""time"
)// ListNode 链表节点定义
type ListNode struct {Val  intNext *ListNode
}// 方法一：分治合并法（推荐）
// 时间复杂度：O(n log k)，空间复杂度：O(log k)
func mergeKLists(lists []*ListNode) *ListNode {if len(lists) == 0 {return nil}if len(lists) == 1 {return lists[0]}return divide(lists, 0, len(lists)-1)
}// 分治递归函数
func divide(lists []*ListNode, left, right int) *ListNode {if left == right {return lists[left]}mid := left + (right-left)/2leftList := divide(lists, left, mid)rightList := divide(lists, mid+1, right)return mergeTwoLists(leftList, rightList)
}// 合并两个有序链表
func mergeTwoLists(l1, l2 *ListNode) *ListNode {dummy := &ListNode{}current := dummyfor l1 != nil && l2 != nil {if l1.Val <= l2.Val {current.Next = l1l1 = l1.Next} else {current.Next = l2l2 = l2.Next}current = current.Next}// 连接剩余节点if l1 != nil {current.Next = l1}if l2 != nil {current.Next = l2}return dummy.Next
}// 方法二：优先队列法（最小堆）
// 时间复杂度：O(n log k)，空间复杂度：O(k)
type NodeHeap []*ListNodefunc (h NodeHeap) Len() int           { return len(h) }
func (h NodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h NodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h *NodeHeap) Push(x interface{}) {*h = append(*h, x.(*ListNode))
}func (h *NodeHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x
}func mergeKListsHeap(lists []*ListNode) *ListNode {if len(lists) == 0 {return nil}// 初始化最小堆h := &NodeHeap{}heap.Init(h)// 将所有非空链表的头节点加入堆for _, list := range lists {if list != nil {heap.Push(h, list)}}dummy := &ListNode{}current := dummy// 依次取出最小节点for h.Len() > 0 {node := heap.Pop(h).(*ListNode)current.Next = nodecurrent = current.Next// 如果该节点有后继，将后继加入堆if node.Next != nil {heap.Push(h, node.Next)}}return dummy.Next
}// 方法三：逐一合并法
// 时间复杂度：O(k*n)，空间复杂度：O(1)
func mergeKListsSequential(lists []*ListNode) *ListNode {if len(lists) == 0 {return nil}result := lists[0]for i := 1; i < len(lists); i++ {result = mergeTwoLists(result, lists[i])}return result
}// 方法四：数组排序法
// 时间复杂度：O(n log n)，空间复杂度：O(n)
func mergeKListsArray(lists []*ListNode) *ListNode {if len(lists) == 0 {return nil}// 收集所有节点值var values []intfor _, list := range lists {current := listfor current != nil {values = append(values, current.Val)current = current.Next}}if len(values) == 0 {return nil}// 排序sort.Ints(values)// 重建链表dummy := &ListNode{}current := dummyfor _, val := range values {current.Next = &ListNode{Val: val}current = current.Next}return dummy.Next
}// 辅助函数：创建链表
func createList(values []int) *ListNode {if len(values) == 0 {return nil}dummy := &ListNode{}current := dummyfor _, val := range values {current.Next = &ListNode{Val: val}current = current.Next}return dummy.Next
}// 辅助函数：打印链表
func printList(head *ListNode) {current := headfor current != nil {fmt.Printf("%d", current.Val)if current.Next != nil {fmt.Print("->")}current = current.Next}fmt.Println()
}// 辅助函数：链表转数组（用于验证结果）
func listToArray(head *ListNode) []int {var result []intcurrent := headfor current != nil {result = append(result, current.Val)current = current.Next}return result
}// 辅助函数：数组比较
func arraysEqual(a, b []int) bool {if len(a) != len(b) {return false}for i := range a {if a[i] != b[i] {return false}}return true
}// 性能测试函数
func measureTime(name string, fn func() *ListNode) *ListNode {start := time.Now()result := fn()duration := time.Since(start)fmt.Printf("%s: 耗时=%v\n", name, duration)return result
}// 运行所有测试用例
func runTests() {fmt.Println("=== 23. 合并K个升序链表 测试用例 ===")// 测试用例1：示例1fmt.Println("\n--- 测试用例1：示例1 ---")lists1 := []*ListNode{createList([]int{1, 4, 5}),createList([]int{1, 3, 4}),createList([]int{2, 6}),}fmt.Println("输入链表：")for i, list := range lists1 {fmt.Printf("链表%d: ", i+1)printList(list)}// 测试所有方法result1_1 := mergeKLists(copyLists(lists1))result1_2 := mergeKListsHeap(copyLists(lists1))result1_3 := mergeKListsSequential(copyLists(lists1))result1_4 := mergeKListsArray(copyLists(lists1))fmt.Println("结果：")fmt.Print("分治合并法: ")printList(result1_1)fmt.Print("优先队列法: ")printList(result1_2)fmt.Print("逐一合并法: ")printList(result1_3)fmt.Print("数组排序法: ")printList(result1_4)// 验证结果一致性expected1 := []int{1, 1, 2, 3, 4, 4, 5, 6}if arraysEqual(listToArray(result1_1), expected1) &&arraysEqual(listToArray(result1_2), expected1) &&arraysEqual(listToArray(result1_3), expected1) &&arraysEqual(listToArray(result1_4), expected1) {fmt.Println("✅ 所有方法结果正确且一致")} else {fmt.Println("❌ 结果不一致！")}// 测试用例2：空数组fmt.Println("\n--- 测试用例2：空数组 ---")lists2 := []*ListNode{}result2 := mergeKLists(lists2)fmt.Printf("结果: %v (预期: null)\n", result2)// 测试用例3：包含空链表fmt.Println("\n--- 测试用例3：包含空链表 ---")lists3 := []*ListNode{nil}result3 := mergeKLists(lists3)fmt.Printf("结果: %v (预期: null)\n", result3)// 测试用例4：单个链表fmt.Println("\n--- 测试用例4：单个链表 ---")lists4 := []*ListNode{createList([]int{1, 2, 3})}result4 := mergeKLists(lists4)fmt.Print("结果: ")printList(result4)// 测试用例5：重复元素fmt.Println("\n--- 测试用例5：重复元素 ---")lists5 := []*ListNode{createList([]int{1, 1, 2}),createList([]int{1, 1, 2}),}result5 := mergeKLists(lists5)fmt.Print("结果: ")printList(result5)// 性能测试fmt.Println("\n--- 性能对比测试 ---")performanceTest()
}// 复制链表数组（因为合并会修改原链表）
func copyLists(lists []*ListNode) []*ListNode {copied := make([]*ListNode, len(lists))for i, list := range lists {copied[i] = copyList(list)}return copied
}// 复制单个链表
func copyList(head *ListNode) *ListNode {if head == nil {return nil}dummy := &ListNode{}current := dummyfor head != nil {current.Next = &ListNode{Val: head.Val}current = current.Nexthead = head.Next}return dummy.Next
}// 性能对比测试
func performanceTest() {// 创建测试数据testLists := []*ListNode{createList([]int{1, 4, 7, 10, 13}),createList([]int{2, 5, 8, 11, 14}),createList([]int{3, 6, 9, 12, 15}),createList([]int{16, 17, 18, 19, 20}),createList([]int{21, 22, 23, 24, 25}),}fmt.Printf("测试数据：5个链表，每个链表5个元素\n")// 测试分治合并法result1 := measureTime("分治合并法", func() *ListNode {return mergeKLists(copyLists(testLists))})// 测试优先队列法result2 := measureTime("优先队列法", func() *ListNode {return mergeKListsHeap(copyLists(testLists))})// 测试逐一合并法result3 := measureTime("逐一合并法", func() *ListNode {return mergeKListsSequential(copyLists(testLists))})// 测试数组排序法result4 := measureTime("数组排序法", func() *ListNode {return mergeKListsArray(copyLists(testLists))})// 验证结果一致性arr1 := listToArray(result1)arr2 := listToArray(result2)arr3 := listToArray(result3)arr4 := listToArray(result4)if arraysEqual(arr1, arr2) && arraysEqual(arr2, arr3) && arraysEqual(arr3, arr4) {fmt.Println("✅ 所有方法结果一致")fmt.Print("合并结果: ")printList(result1)} else {fmt.Println("❌ 结果不一致！")}
}// 展示分治过程
func demonstrateDivideConquer() {fmt.Println("\n--- 分治过程演示 ---")lists := []*ListNode{createList([]int{1, 4}),createList([]int{1, 3}),createList([]int{2, 6}),createList([]int{5, 7}),}fmt.Println("原始4个链表：")for i, list := range lists {fmt.Printf("链表%d: ", i+1)printList(list)}fmt.Println("\n分治合并过程：")fmt.Println("第1轮：合并相邻链表对")merged1 := mergeTwoLists(copyList(lists[0]), copyList(lists[1]))merged2 := mergeTwoLists(copyList(lists[2]), copyList(lists[3]))fmt.Print("合并链表1+2: ")printList(merged1)fmt.Print("合并链表3+4: ")printList(merged2)fmt.Println("\n第2轮：合并结果")final := mergeTwoLists(merged1, merged2)fmt.Print("最终结果: ")printList(final)
}func main() {runTests()demonstrateDivideConquer()
}