题目描述

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个有序单链表，然后返回这个新链表。分析时间复杂度、空间复杂度。

题解

暴力破解

将链表转换成数组，然后将数组排序，最后根据数组中的顺序依次生成结果链表中的节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        vector<int> arr;
        
        for (ListNode* list : lists){
            while (list){
                arr.push_back(list->val);
                list = list->next;
            }
        }
        sort(arr.begin(), arr.end());
        ListNode *first = new ListNode(-1), *node = first;
        
        for (int val : arr){
            node->next = new ListNode(val);
            node = node->next;
        }
        
        return first->next;
    }
};

时间复杂度：O(NlogN)。

空间复杂度：O(N).

优先队列

同时进行k个链表的合并，通过将每个链表的头结点放入优先队列中（同时完成了排序），弹出节点，将节点并入结果链表中，如果当前节点仍不为空，则将下一个节点压入优先队列中。

/**
 * 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) {
        auto cmp = [](ListNode* &l1, ListNode* &l2){
            return l1->val > l2->val;
        };
        // 定义一个小顶堆
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
        
        for (auto node: lists){
            if(node) q.push(node);
        }
        ListNode* dummy = new ListNode(-1), *cur = dummy;
        
        while (!q.empty()){
            auto t = q.top(); q.pop();
            cur->next = t;
            cur = cur->next;
            if (t->next) q.push(t->next);
        }
        
        return dummy->next;
    }
};

时间复杂度：O(Nlogk)

空间复杂度：O(N)新链表所用空间；O(k)优先队列所占空间。

两两合并

类似于分治法，不断进行两两合并，直到只剩最后一个链表，这个链表就为最终的结果链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        
        int size = lists.size();
        
        while (size > 1){
            int k = (size + 1)/2;
            for (int i=0; i< size/2; i++)
                lists[i] = merge(lists[i], lists[i+k]);
            size = k;
        }
        
        return lists[0];
    }
private:
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode *first = new ListNode(-1);
        ListNode *node = first;
        
        while(l1 && l2){
            if (l1->val < l2->val){
                node->next = l1;
                l1 = l1->next;
            }
            else{
                node->next = l2;
                l2 = l2->next;
            }
            node = node->next;
        }
        if (l1) node->next = l1;
        if (l2) node->next = l2;
        
        return first->next;
    }
};

时间复杂度：O(Nlogk)

空间复杂度：O(1)