面试题26：合并k个排好序的单链表

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

 1 class Solution {
 2 public:
 3     ListNode *mergeKLists(vector<ListNode *> &lists) {
 4         int n = lists.size();
 5         if(n == 0) return nullptr;
 6         if(n == 1) return lists[0];
 7         return mergeKLists(lists,0,n-1);
 8     }
 9     ListNode* mergeKLists(vector<ListNode*> &lists,int l,int r){
10         if(l > r) return nullptr;
11         if(l == r) return lists[l];
12 
13         int mid = l + (r-l)/2;
14         ListNode* left = mergeKLists(lists,l,mid);
15         ListNode* right = mergeKLists(lists,mid+1,r);
16 
17         return merge(left,right);
18     }
19 
20     ListNode* merge(ListNode* l1,ListNode* l2){
21         ListNode* dummy = new ListNode(-1);
22         ListNode* p = dummy;
23         while(l1 && l2){
24             if(l1->val <= l2->val){
25                 p->next = l1;
26                 l1 = l1->next;
27                 p = p->next;
28             }else{
29                 p->next = l2;
30                 l2 = l2->next;
31                 p = p->next;
32             }
33         }
34         if(l1) p->next = l1;
35         if(l2) p->next = l2;
36         return dummy->next;
37 
38     }
39 };