Skip to content

0023. 合并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\)

解答

法一：分治+递归

我们可以使用分治的思想来合并k个升序链表。具体步骤如下：

  1. 首先定义一个辅助函数mergeTwoLists，用于合并两个有序链表。该函数的实现可以参考这道题0021. 合并两个有序链表。
  2. 然后定义一个递归函数divide，用于将链表数组划分为两部分，并递归地合并每一部分。具体来说，divide函数接受链表数组和左右边界作为参数，如果左右边界相等，则返回对应的链表；否则，计算中间位置，将链表数组划分为左半部分和右半部分，递归地调用divide函数合并这两部分，最后使用mergeTwoLists函数将合并后的两部分链表合并起来。
  3. 最后，在主函数mergeKLists中，首先检查链表数组是否为空或只有一个链表，如果是，则直接返回对应的链表；否则，调用divide函数进行合并，并返回最终的合并结果。
class Solution {
private:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;

        if(list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else{
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }

    ListNode* divide(vector<ListNode*>& lists,int left,int right){
        if(left  == right)  return lists[left];

        int mid = left + (right - left)/2;

        ListNode* lpart = divide(lists,left,mid);
        ListNode* rpart = divide(lists,mid+1,right);

        return mergeTwoLists(lpart,rpart);
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())  return NULL;
        if(lists.size()==1)  return lists[0];
        return divide(lists,0,lists.size()-1);

    }
};

const mergelist = (l1,l2) =>{
    const dummy = new ListNode(0);
    let curr = dummy;

    while(l1 && l2){
        if(l1.val < l2.val){
            curr.next = l1;
            l1 = l1.next;
        }else{
            curr.next = l2;
            l2 = l2.next;
        }

        curr = curr.next;
    }

    curr.next = l1 || l2;
    return dummy.next;
}

var mergeKLists = function(lists) {
    if(lists.length === 0)  return null;

    const mergediv = (left,right) =>{
        if(left === right)  return lists[left];

        const mid = Math.floor((left+right)/2);
        const l1 = mergediv(left,mid);
        const l2 = mergediv(mid+1,right);

        return mergelist(l1,l2);
    }
    return mergediv(0,lists.length-1);
};

法二：优先队列

我们可以使用优先队列（最小堆）来合并k个升序链表。具体步骤如下：

  1. 定义一个比较器Compare，用于在优先队列中比较链表节点的值，以实现最小堆的功能。
  2. 在主函数mergeKLists中，首先创建一个优先队列minHeap，并使用比较器Compare进行初始化。
  3. 遍历链表数组，将每个非空链表的头节点加入优先队列中。
  4. 创建一个虚拟头节点dummy，用于构建合并后的链表，并使用一个指针tail指向当前合并链表的尾部。
  5. 当优先队列不为空时，执行以下操作：
    • 从优先队列中取出堆顶的最小节点minNode。
    • 将minNode连接到合并链表的尾部，并更新tail指针。
    • 如果minNode有下一个节点，则将其加入优先队列中。
  6. 最后，返回合并链表的头节点，即dummy->next。
class Solution {
public:
    struct Compare{
        bool operator()(ListNode* a,ListNode* b){
            return a->val > b->val; 
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,Compare> minHeap;

        for (ListNode* node : lists) {
            if (node != nullptr) {
                minHeap.push(node);
            }
        }

        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;

        while (!minHeap.empty()) {
            ListNode* minNode = minHeap.top(); // 取出堆顶的最小节点
            minHeap.pop();

            tail->next = minNode; // 把最小节点拼到结果链表的尾部
            tail = tail->next;    // 尾指针向后移动

            // 如果当前节点还有下一个节点，就把它加入堆
            if (minNode->next != nullptr) {
                minHeap.push(minNode->next);
            }
        }

        ListNode* result = dummy->next;
        delete dummy; 
        return result;
    }
};