LeetCode 23. 合并 K 个升序链表
题目描述
思路分析
归并排序
参考代码
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
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
} else 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 {
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
} else {
l2.Next = mergeTwoLists(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
33
34
35
36
37
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
} else 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 {
if l1 == nil {
return l2
} else if l2 == nil {
return l1
}
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
}
1
write your code here
相似题目
题目 | 难度 | 题解 |
---|---|---|
合并两个有序链表 | Easy | |
丑数 II | Medium |
CC BY-NC-SA 4.0
许可协议,转载请注明出处!
本博客所有文章除特别声明外,均采用