跳转至

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

Reference

题解

最直接的合并思路是按照顺序对链表进行合并。考虑到合并后链表变长，平均每次合并需要花费\(\mathcal O(MN)\)的时间，共需合并\(\mathcal O(M)\)次，因此总的时间复杂度为\(\mathcal O(M^2N)\)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2);
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if (!listsSize)
        return NULL;
    struct ListNode *head = lists[0];
    for (int i = 1; i<listsSize; i++)
    {
        if (!head)
        {
            head = lists[i];
            continue;
        }
        head = mergeLists(head, lists[i]);
    }
    return head;
}

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2){
    if (!l1)
        return l2;
    if (!l2)
        return l1;
    if (l1->val < l2->val)
    {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    }
    else
    {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}

如果使用两两合并的方式，可以将合并操作的平均时间复杂度降低至\(\mathcal O(N\log M)\)，总的时间复杂度变为\(\mathcal O(MN\log M)\)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2);
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if (!listsSize)
        return NULL;
    else if (listsSize == 1)
        return lists[0];
    else if (listsSize == 2)
        return mergeLists(lists[0], lists[1]);
    struct ListNode *head = lists[0];
    int step = (listsSize + 1) >> 1;
    for (int i = 0; i < step; i++)
    {
        if (i + step < listsSize)
            lists[i] = mergeLists(lists[i], lists[i + step]);
    }
    return mergeKLists(lists, step);
}

struct ListNode* mergeLists(struct ListNode* l1, struct ListNode* l2){
    if (!l1)
        return l2;
    if (!l2)
        return l1;
    if (l1->val < l2->val)
    {
        l1->next = mergeLists(l1->next, l2);
        return l1;
    }
    else
    {
        l2->next = mergeLists(l1, l2->next);
        return l2;
    }
}

评论