Merge k Sorted Lists，mergesortedlists
題目：Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路：我的第一個想法是將lists中的鏈表兩兩合並排序，這樣時間復雜度是o（n），n為所有鏈表中的數據，結果Time Limit Exceeded了。。。暫時沒有想到太好的其他方法，希望有大神能給點思路，我先拋個磚，以下是我未AC的代碼：
![]()
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode *mergeKLists(vector<ListNode *> &lists) {
12 if(lists.size() == 0) return NULL;
13
14 ListNode *pList=lists[0];
15
16 vector<ListNode *>::iterator it=lists.begin()+1;
17 for(;it!=lists.end();++it)
18 {
19 pList=MergeLists(pList,*it);
20 }
21
22 //for(int i=1;i<lists.size();i++)
23 //{
24 //pList=MergeLists(pList,lists[i]);
25 //}
26
27 return pList;
28 }
29
30 ListNode *MergeLists(ListNode *list1, ListNode *list2)
31 {
32 ListNode *pList=new ListNode(0);
33 ListNode *pHead=pList;
34
35 while(list1 && list2)
36 {
37 if(list1->val > list2->val)
38 {
39 pList->next=list2;
40 list2=list2->next;
41 }
42 else
43 {
44 pList->next=list1;
45 list1=list1->next;
46 }
47 pList=pList->next;
48 }
49
50 if(!list1)
51 {
52 pList->next=list2;
53 }
54 if(!list2)
55 {
56 pList->next=list1;
57 }
58
59 pList=pHead;
60 pList=pList->next;
61 pHead->next=NULL;
62 delete(pHead);
63
64 return pList;
65 }
66 };
View Code
