leetcode
分治思想
时间复杂度：O(kn * log k)
空间复杂度：O(log 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
func mergeKLists(lists []*ListNode) *ListNode {
k := len(lists)
if k == 0 {
return nil
}
if k == 1 {
return lists[0]
}
mid := k / 2
left := lists[0:mid]
right := lists[mid:k]
leftList := mergeKLists(left)
rightList := mergeKLists(right)
return merge(leftList, rightList)
}
func merge(left *ListNode, right *ListNode) *ListNode{
dummy := &ListNode{}
result := dummy
for left != nil && right != nil {
if left.Val < right.Val {
dummy.Next = left
dummy = left
left = left.Next
}else{
dummy.Next = right
dummy = right
right = right.Next
}
}
if left == nil {
dummy.Next = right
}
if right == nil {
dummy.Next = left
}
return result.Next
}
|