23. Merge k Sorted Lists

description:

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

Example:

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

my answer:

感恩

两个两个合并，并行工作

0-3，1-4，2-5
0，  1，  2
0-2，1
0，  1
0-1
0

大佬的answer：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;
        int n = lists.size();
        while(n > 1){
            int k = (n + 1) / 2;
            for(int i = 0; i < n/2; i++){
                lists[i] = merge2lists(lists[i], lists[i + k]);
            }
            n = k;
        }return lists[0];
    }
    
    ListNode* merge2lists(ListNode* list1, ListNode* list2){
        ListNode* dummy = new ListNode(-1), *cur = dummy;
        while(list1 && list2){
            if(list1->val>list2->val){
                cur->next = list2;
                list2 = list2->next;
            }else{
                cur->next = list1;
                list1 = list1->next;
            }
            cur = cur->next;
        }
        if(list1) cur->next = list1;
        if(list2) cur->next = list2;
        return dummy->next;
    }
};

relative point get√：

hint :