Merge k Sorted Lists

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

C++:
01 /**
02  * Definition for singly-linked list.
03  * struct ListNode {
04  *     int val;
05  *     ListNode *next;
06  *     ListNode(int x) : val(x), next(NULL) {}
07  * };
08  */
09  void mergeKListsHelper(ListNode*& head, ListNode*& end,
10                         ListNode* item)
11  {
12      if(head==NULL)
13      {
14          head=end=item;
15      }
16      else
17      {
18          end->next=item;
19          end=item;
20      }
21  }
22 class Solution {
23 public:
24     ListNode *mergeKLists(vector<ListNode *> &lists) {
25         // Start typing your C/C++ solution below
26         // DO NOT write int main() function
27         ListNode* result=NULL;
28         ListNode* end=NULL;
29         while(true)
30         {
31             bool flag=false;
32             int min=INT_MAX;
33             int j=0;
34             for(int i=0;i<lists.size();i++)
35             {
36                 if(lists[i]!=NULL)
37                 {
38                     flag=true;
39                     if(lists[i]->val<min)
40                     {
41                         min=lists[i]->val;
42                         j=i;
43                     }
44                 }
45             }
46             if(flag==false)
47                 break;
48             ListNode* item=lists[j];
49             lists[j]=lists[j]->next;
50             mergeKListsHelper(result,end,item);
51         }
52         return result;
53     }
54 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s