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];} |
原文：http://www.cnblogs.com/lautsie/p/3525821.html