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-50，  1，  20-2，10，  10-10

大佬的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
    
     & 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 :