merge sort，leet code里面曾经做过。但一开始没这么写，遍历来做，效率n*k了，用了merge sort后，变成logn*k。
用了dummy node。同时要注意size为0的情况。
|
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
|
#include <climits>/*链表结点的定义(请不要在代码中定义该类型)struct ListNode { int val;
ListNode *next;
};*///lists包含k个链表的头结点,返回合并后链表头结点ListNode* merge(vector<ListNode*> &lists) { if
(lists.size() == 0) return
NULL;
int
k = 1;
while
(k < lists.size()) {
for
(int
i = 0; i < lists.size(); i += k*2) {
int
j = i + k;
if
(j >= lists.size()) break;
// merge list i and j
ListNode *dummy = new
ListNode();
ListNode *last = dummy;
while
(lists[i] != NULL && lists[j] != NULL) {
if
(lists[i]->val < lists[j]->val) {
last->next = lists[i];
last = last->next;
lists[i] = lists[i]->next;
} else
{
last->next = lists[j];
last = last->next;
lists[j] = lists[j]->next;
}
}
while
(lists[i] != NULL) {
last->next = lists[i];
last = last->next;
lists[i] = lists[i]->next;
}
while
(lists[j] != NULL) {
last->next = lists[j];
last = last->next;
lists[j] = lists[j]->next;
}
last->next = NULL;
lists[i] = dummy->next;
delete
dummy;
}
k *= 2;
}
return
lists[0];
} |