老卫带你学---leetcode刷题(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
1
2
3
4
5
6
7
8
9
10
11
12

示例 2：

输入：lists = []
输出：[]
示例 3：

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

提示：

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
5
6
7
8

解决：

没什么说的，分治+递归
通过分治将k问题，分解为多个TwoList合并问题（老卫带你学—剑指offer刷题系列(16.合并两个排序的链表)），然后递归下去

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists)==0{
		return nil
	}
	return merge(lists,0,len(lists)-1)
}

func merge(lists []*ListNode,l,r int) *ListNode{
	if l==r{
		return lists[l]
	}
	mid := l+(r-l)/2
	l1 := merge(lists,l,mid)
	l2:=merge(lists,mid+1,r)
	return mergeTwoList(l1, l2)
}

func mergeTwoList(l1,l2 *ListNode) *ListNode{
	if l1==nil{
		return l2
	}
	if l2==nil{
		return l1
	}
	if l1.Val<l2.Val{
		l1.Next=mergeTwoList(l1.Next, l2)
		return l1
	} else{
		l2.Next=mergeTwoList(l1,l2.Next)
		return l2
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32