Merge k Sorted Lists

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

C++:
01 void enList(ListNode*& head, ListNode*& tail, ListNode* p)
02 {
03      if(p==NULL)
04          return;
05      if(head==NULL){
06          head=tail=p;
07      }else{
08          tail->next=p;
09          tail=p;
10      }
11 }
12 
13 ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
14 {
15      if(l1==NULL)
16          return l2;
17      if(l2==NULL)
18          return l1;
19      ListNode* a=l1;
20      ListNode* b=l2;
21      ListNode* head=NULL;
22      ListNode* tail=NULL;
23      while(a&&b){
24          if(a->val<=b->val){
25              enList(head,tail,a);
26              a=a->next;
27          }else{
28              enList(head,tail,b);
29              b=b->next;
30          }
31      }
32      if(a){
33          tail->next=a;
34      }else{
35          tail->next=b;
36      }
37      return head;
38 }
39 
40  ListNode *mergeKLists(vector<ListNode *> &lists)
41  {
42      int n=lists.size();
43      if(n==0)
44          return NULL;
45      ListNode* head=lists[0];
46      for(int i=1;i<n;i++)
47          head=mergeTwoLists(head,lists[i]);
48      return head;
49 }
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