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

 

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     11 public:12     ListNode* mergeKLists(vector
     
      & lists) {13         int k = lists.size();14         if (k == 0) return NULL;15         16         while (k > 1){17             for (int i = 0; i < k /2; i++){18                 lists[i] = mergeTwoLists(lists[i], lists[k-1-i]);19             }20             if (k%2){21                 k = k/2 + 1;22             }else{23                 k = k / 2;24             }25         }26         27         return lists[0];28     }29     30 private:31     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {32         ListNode *dummy = new ListNode(0);33         ListNode *ret = NULL;34         35         36         ListNode *p1 = l1;37         ListNode *p2 = l2;38         39         ListNode *p = dummy;40         41         while(p1 && p2){42             if (p1->val < p2->val){43                 p->next = p1;44                 p1 = p1->next;45             }else{46                 p->next = p2;47                 p2 = p2->next;48             }49             p = p->next;50         }51         52         p1 = (!p1) ? p2 : p1;53         54         while (p1){55             p->next = p1;56             // don't forget to move p1 !!57             p1 = p1->next;58             p = p->next;59         }60         61         ret = dummy->next;62         delete dummy;63         return ret;64     }65 };