23. 合并K个升序链表

题目#

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

思路#

按说该用堆来做的，但 go 里建堆太复杂了，所以用了分治法完成。

将 k 个链表分为两个两个的链表互相合并（合并两个链表的题是 21. 合并两个有序链表），如果是奇数个，则多出来的轮空一下。

不过倒是用 C++ 写了堆版本的代码。

代码#

分治（go）#

func mergeKLists(lists []*ListNode) *ListNode {
    length := len(lists)
    if length == 0 {
        return nil
    }
    if length == 1 {
        return lists[0]
    }

    num := length / 2
    left := mergeKLists(lists[:num])
    right := mergeKLists(lists[num:])

    return mergeTwoLists(left, right)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    var l *ListNode
    if l1.Val < l2.Val {
        l = l1
        l.Next = mergeTwoLists(l1.Next, l2)
    } else {
        l = l2
        l.Next = mergeTwoLists(l1, l2.Next)
    }

    return l
}

堆（C++）#

C++ 中的优先队列本身就是基于堆的，因此直接调用就好

#include "ListNode.hpp"
#include <vector>
#include <queue>

using namespace std;

class Solution
{
public:
    struct Status
    {
        int val;
        ListNode *node;
        // 重载运算符，使较小的更优先
        bool operator<(const Status &rhs) const
        {
            return val > rhs.val;
        }
    };

    priority_queue<Status> q;

    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        for (auto node : lists)
        {
            if (node != nullptr)
            {
                q.push({node->val, node});
            }
        }

        ListNode head, *tail = &head;

        while (!q.empty())
        {
            auto f = q.top();
            q.pop();

            tail->next = f.node;
            tail = tail->next;
            if (f.node->next != nullptr)
            {
                q.push({f.node->next->val, f.node->next});
            }
        }
        return head.next;
    }
};