题目描述

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

样例

相关题型

合并两个排序链表(简单)

算法思路：二分+归并排序

主函数功能是讲k个链表进行合并排序，我们先递归合并排序 左一半的链表 和 右一半的链表。最后将两个链表进行归并排序。

时间复杂度 递归合并：$O(logn)& 归并排序：&O(n)&,则总时间为：&O(n*logn)&

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* merge_lists(ListNode* left, ListNode* right) //归并排序两个有序链表
    {
        auto dummy = new ListNode(-1);
        auto p = dummy;
        auto i = left, j = right;
        while(i && j)
        {
            if(i -> val <= j->val){
                p -> next = i;
                p = i;
                i = i->next;
            }
            else{
                p -> next = j;
                p = j;
                j = j->next;
            }
        }
        while(i){
            p -> next = i;
            p = i;
            i = i->next;
        }
        while(j){
            p -> next = j;
            p = j;
            j = j->next;
        }
        return dummy->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) { //递归合并长度为k的链表
        if(lists.empty()) return NULL;
        if(lists.size() == 1) return lists[0];
        int mid = lists.size() / 2;
        auto left = vector<ListNode*> (lists.begin(), lists.begin()+mid);
        auto right = vector<ListNode*> (lists.begin()+mid, lists.end());
        auto l = mergeKLists(left);
        auto r = mergeKLists(right);

        return merge_lists(l, r);
    }
};