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

想法很简单，就是两两合并。在Merge Two Sorted Lists这道题已经实现了两两合并的代码了，就直接拿过来用。

假设每条链平均长度为n，如果用二分法的话， 也就是将所有的链分成两份，每份各自合并完之后再合并起来。递归的空间复杂度会是O(logk)， 时间复杂度T(k)=2T(k/2) +O(nk)，由主定理得O(nklgk)。

主定理见。

下面是两两合并的代码，时间复杂度是$O(2n+3n+\ldots+kn)=O(k^2n)$.

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
     
       &lists) {12         if (lists.empty()) return NULL;13         ListNode* head = lists[0];14         for (int i = 1; i < lists.size(); ++i) {15             head = mergeTwoLists(head, lists[i]);16         }17         18         return head;19     }20     21     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {22         ListNode *head, *t3;23         head = t3 = new ListNode(0);24         while (l1 != NULL && l2 != NULL) {25             if (l1->val <= l2->val) {26                 t3->next = l1;27                 l1 = l1->next;28             } else {29                 t3->next = l2;30                 l2 = l2->next;31             }32             t3 = t3->next;33         }34         35         while (l1 != NULL) {36             t3->next = l1;37             t3= t3->next;38             l1 = l1->next;39         }40         while (l2 != NULL) {41             t3->next = l2;42             t3 = t3->next;43             l2 = l2->next;44         }45         46         ListNode *ret = head->next;47         delete head;48         return ret;49     }50 };
     

 下面是二分的实现。

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 *mergeTwoLists(ListNode *l1, ListNode *l2) {12         ListNode h(0), *p = &h;13         while (l1 || l2) {14             if (l1 == NULL || (l2 != NULL && l2->val < l1->val)) {15                 p->next = l2;16                 l2 = l2->next;17             } else {18                 p->next = l1;19                 l1 = l1->next;20             }21             p = p->next;22         }23         return h.next;24     }25     ListNode *mergeKLists(vector
     
       &lists) {26             if (lists.empty()) return NULL;27             28             vector
      
       
         > layers(2);29             int cur = 0, next = 1;30             layers[cur] = lists;31             while (layers[cur].size() > 1) {32                 layers[next].clear();33                 for (int i = 0; i < layers[cur].size(); i += 2) {34                     if (i + 1 < layers[cur].size()) layers[next].push_back(mergeTwoLists(layers[cur][i], layers[cur][i + 1]));35                     else layers[next].push_back(layers[cur].back());36                 }37                 cur = !cur; next = !next;38             }39             return layers[cur][0];40     }41 };
       
      
     

非递归的空间复杂度可以优化到O(k)。