Merge k Sorted Lists -- leetcode

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

算法一，自底至顶递归。

时间复杂度为O(nlogk)。

空间复杂度为O(k)。

此算法在leetcode上实际执行时间为 144ms (130 test cases)。

/**
 * 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 0;
        if (lists.size() == 1) return lists.back();

        vector
   
     l; while (!lists.empty()) { if (lists.size() == 1) { l.push_back(lists.back()); lists.pop_back(); } else { ListNode *p = lists.back(); lists.pop_back(); ListNode *q = lists.back(); lists.pop_back(); l.push_back(merge(p, q)); } } return mergeKLists(l); } ListNode *merge(ListNode *p,ListNode *q) { ListNode fake(0); ListNode *m = &fake; while (p && q) { if (p->val < q->val) { m->next = p; p = p->next; } else { m->next = q; q = q->next; } m = m->next; } m->next = p ? p : q; return fake.next; } };