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

AC code:

/** * 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.size() == 0) {            return nullptr;        }        while (lists.size() > 1) {            lists.push_back(mergeTowLists(lists[0], lists[1]));            lists.erase(lists.begin());            lists.erase(lists.begin());        }        return lists.front();    }        ListNode* mergeTowLists(ListNode* first, ListNode* second) {        if (first == nullptr) {            return second;        }         if (second == nullptr) {            return first;        }        // 这个地方first是一个指向链表的指针所以用->而不用.        if (first->val <= second->val) {            // 这里的递归调用，当满足条件的时候mergeTowLists()可以先不用管，最后递归出来的时候会将满足条件的链表返回            // 可以先从递归的最后一个条件考虑            first->next = mergeTowLists(first->next, second);            return first;        } else {            second->next = mergeTowLists(first, second->next);            return second;        }    }};
     

Runtime: 56 ms, faster than 26.25% of C++ online submissions for Merge k Sorted Lists.

 

　　　　　　　　　　　　　　　　　　递归的最后一个：

return:　　　　　　　　　　　　　　　　　　    ->  6

return:　　　　　　　　　　　　　　　  ->   5    ->   6

　　　　　　　　　　　　　　　　　4   ->   5    ->   6

　　　　　　　　　　　　. . . . .

return 　1  ->  1  ->  2  ->  3  ->  4  ->   4   ->   5　->   6