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

Example:Input:[  1->4->5,  1->3->4,  2->6]Output: 1->1->2->3->4->4->5->6

合并k个有序链表。

用归并排序就好了。

1 class Solution { 2 public: 3     ListNode* merge(vector
     
      & lists, int low, int high) { 4         ListNode* left = nullptr; 5         ListNode* right = nullptr; 6         if (low < high - 1) { 7             int mid = low + (high - low) / 2; 8             left = merge(lists, low, mid); 9             right = merge(lists, mid+1, high);10         }11         else {12             left = lists[low];13             right = low == high? nullptr: lists[high];14         }15         int a, b; 16         ListNode *res = new ListNode(0);17         ListNode *curr = res;18         while (left || right) {19             a = left? left->val: INT_MAX;20             b = right? right->val: INT_MAX;21             if (a < b) {22                 curr->next = left;23                 left = left->next;24                 curr = curr->next;25             }26             else {27                 curr->next = right;28                 right = right->next;29                 curr = curr->next;30             }31         }32         curr = res->next;33         delete res;34         return curr;35     }36     ListNode* mergeKLists(vector
      
       & lists) {37         ListNode *head = nullptr;38         int low = 0;39         int high = lists.size() - 1;40         if (low <= high)41             head = merge(lists, low, high);42         return head;43     }44 };