合并K个升序链表（LeetCode 23）

1.问题描述

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

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

示例 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
1
2
3
4
5
6
7
8
9
10

示例 2：

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

示例 3：

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

2.难度等级

Hard。

3.热门指数

★★★★☆

4.解题思路

方法一：顺序合并

我们可以想到一种最朴素的方法，依次将链表数组中的链表与最终结果合并。问题便退化成合并两个有序链表。

如何合并两个有序链表呢？

遍历两个链表选择值较小的结点链接到结果链表中即可。当一个节点被添加到结果链表之后，将对应链表中的节点向后移一位。

为了简化对结果链表边界条件的判断，可以引入哨兵结点。哨兵结点的 Next 指针便是结果链表的头结点。

遍历 list1 或 list2 链表，选择 list1 与 list2 链表当前结点值较小的结点，挂接到结果链表，并将较小结点后移一位。
如果有一个为空，结束遍历，则将未遍历完的链表，直接挂接到结果链表。

时间复杂度： 假设每个链表的最长长度是 n。在第一次合并后，结果链表的长度为 n；第二次合并后，结果链表的长度为 2n，第 i 次合并后，结果链表的长度为 in。第 i 次合并的时间代价是 O(n+(i−1)×n)= O(in)，那么总的时间代价为
$$O(\sum _{i=1}^k(i\times n))=O(\frac{(1+k)\cdot k}{2}\times n)=O(k^{2}n)$$
故渐进时间复杂度为 $O(k^{2}n)$，其中 k 为链表个数。

空间复杂度： 没有用到与 k 和 n 规模相关的辅助空间，故渐进空间复杂度为 O(1)。

下面以 Golang 为例给出实现。

func merge(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	tail, h1, h2 := dummyHead, head1, head2
	for h1 != nil && h2 != nil {
		if temp1.Val < temp2.Val {
			tail.Next = h1
			h1= h1.Next
		} else {
			tail.Next = h2
			h2= h2.Next
		}
		tail = tail.Next
	}
	if h1 != nil {
		tail.Next = h1
	} else {
		tail.Next = h2
	}
	return dummyHead.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	var head *ListNode
	for _, l := range lists {
		head = merge(head, l)
	}
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

方法二：分治合并

可以优化方法一，采用分治的方法进行合并。

• 将 k 个链表配对并将同一对中的链表合并；
• 第一轮合并以后， k 个链表被合并成了 $\frac{k}{2}$个链表，然后是 $\frac{k}{4}$ 个链表， $\frac{k}{8}$ 个链表等等。
  重复这一过程，直到我们得到了最终的有序链表。
• 重复这一过程，直到我们得到最终的有序链表。

时间复杂度： 考虑递归「向上回升」的过程，每一轮合并的时间复杂度都是 O(kn)，需要合并 logk 轮，所以总的时间复杂度是 O(kn*logk)。

空间复杂度： 递归会使用到 O(log⁡k) 空间代价的栈空间。

下面以 Golang 为例给出实现。

func divideMerge(lists []*ListNode, l, r int) *ListNode {
	if l == r {
		return lists[l]
	}

	mid := (l + r) / 2
	// 合并左链表
	lhead := divideMerge(lists, l, mid)
	// 合并右链表
	rhead := divideMerge(lists, mid+1, r)
	// 合并左右链表
	return merge(lhead, rhead)
}

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	return divideMerge(lists, 0, len(lists)-1)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法三：使用优先队列合并

这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。

时间复杂度： 考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(log⁡k)，这里最多有 kn 个结点，对于每个结点都被插入删除各一次，故总的时间代价为 O(kn*log⁡k)。

**空间复杂度：**这里用了优先队列，优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)。

下面以 C++ 为例给出实现。

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        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) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top();
            q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) {
            	q.push({f.ptr->next->val, f.ptr->next});
            }
        }
        return head.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

参考文献

23. 合并K 个升序链表 - LeetCode