DS单链表_合并k个升序链表

题目描述

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

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

示例

输入：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

算法

(归并) $O(Nlogk)$

首先，我们对所有链表的头节点进行归并排序。

找到所有链表中最小的头节点，将其移动到合并链表的末尾。

重复此过程，直到所有节点都被合并为一个链表。

时间复杂度

时间复杂度为 $O(Nlogk)$，其中 $N$ 是所有链表中的节点总数，$k$ 是链表的数量。

空间复杂度

空间复杂度为 $O(1)$。

参考文献

Python 代码

class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists:
return None

n = len(lists)
while n > 1:
k = (n + 1) // 2
for i in range(n // 2):
lists[i] = self.mergeTwoLists(lists[i], lists[i + k])
n = k

return lists[0]

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 if l1 else l2

dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next

tail.next = l1 if l1 else l2
return dummy.next