Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]

Output: 1->1->2->3->4->4->5->6

合并并排序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
class Solution {
public:
ListNode * mergeKLists(vector<ListNode*>& lists) {
return partition(lists, 0, lists.size() - 1);
}

ListNode* partition(vector<ListNode*> & lists, int start, int end){
if(start == end)
return lists[start];
if(start < end) {
int mid = (start + end) / 2;
ListNode * l1 = partition(lists, start, mid);
ListNode * l2 = partition(lists, mid+1, end);
return mergeTwoLists(l1, l2);
}
return NULL;
}


ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode * p = NULL;
ListNode * l3 = new ListNode(-1); // create a new node
p = l3; // use to traverse

if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
if(l1 == NULL && l2 == NULL) return NULL;

while(l1 && l2) {
if( l1->val >= l2->val){ // add smaller node into l3
p->next = l2;
p = l2; // move to the newest node in l3
l2 = l2->next;
}
else {
p->next = l1;
p = l1;
l1 = l1->next;
}
if(!l1) p ->next = l2;
if(!l2) p ->next = l1;
}
return l3->next;
}
};