题解 | #合并k个已排序的链表#

方法一：归并排序

利用双指针和分治（递归）的思想来求解

可以将问题分解为两个有序链表的合并的小问题，并且不断地向上递归，最终就可以将K个链表按顺序合并到一起。

时间复杂度：o(nlog^k)；递归有log^k层，n为所有链表的总结点数，复杂度为o(nlog^k)。

空间复杂度：o(log^k)，需要log^k的递归栈。

class Solution {
  public:
  	//合并两个有序链表
    ListNode* merge(ListNode* phead1, ListNode* phead2) {
        if (phead1 == nullptr)
            return phead2;
        if (phead2 == nullptr)
            return phead1;

        ListNode* res = new ListNode(0);
        ListNode* cur = res;
        while (phead1 && phead2) {
            if (phead1->val < phead2->val) {
                cur->next = phead1;
                phead1 =  phead1->next;
            } else {
                cur->next = phead2;
                phead2 = phead2->next;
            }
            cur = cur->next;
        }

        if (phead1)
            cur->next = phead1;
        if (phead2)
            cur->next = phead2;

        return res->next;
    }

    ListNode* divideLists(vector<ListNode*>& lists, int left, int right) {
	  	//特殊情况处理
        if (left > right)
            return nullptr;
        if (left == right)
            return lists[left];

        int mid = (left + right) / 2;
	  	//拆分为子问题，并且向上递归，最终的合并所有的链表
        return merge(divideLists(lists, left, mid), divideLists(lists, mid + 1, right));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideLists(lists, 0, lists.size() - 1);
    }
};

方法二：辅助空间排序

1、创建数组，将K个链表存储到数组中；

2、对数组中的元素进行排序（快排）；

3、将数组转换为链表即得到按顺序合并后的链表。

时间复杂度：o(nlogⁿ)。遍历需要的时间为o(n)；快排需要的时间为o(nlogⁿ)。

空间复杂度：o(n)。需要辅助数组存储所有链表的结点的值。

class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return nullptr;
        if (lists.size() == 1)
            return lists[0];

        vector<int> vect;
        for (int i = 0; i < lists.size(); i++) {
            ListNode* temp = lists[i];
            while (temp) {
                vect.push_back(temp->val);
                temp = temp->next;
            }
        }
        sort(vect.begin(), vect.end());

        ListNode*  res = new ListNode(0);
        ListNode* phead = res;
        for (int i = 0; i < vect.size(); i++) {
            phead->next = new ListNode(vect[i]);
            phead = phead->next;
        }
        phead->next = nullptr;

        return res->next;
    }
};

拓展思路

方法三：小顶堆