目录

0023:合并 K 个升序链表(★★)

力扣第 23 题

题目

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

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

示例 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

相似问题:

分析

#1

本题类似于归并排序,可以用分治法,归并过程即 0021

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        n = len(lists)
        if n<2:
            return lists[0] if lists else None
        a, b = self.mergeKLists(lists[:n//2]), self.mergeKLists(lists[n//2:])
        dum = p = ListNode()
        while a and b:
            if a.val<=b.val:
                p.next = a
                a = a.next
            else:
                p.next = b
                b = b.next
            p = p.next
        p.next = a or b
        return dum.next

53 ms

#2

还可以用堆进行多路归并,堆里维护每个链表的头节点值和链表下标即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        pq = sorted((a.val,i) for i,a in enumerate(lists) if a)
        dum = p = ListNode()
        while pq:
            _,i = heappop(pq)
            p.next = lists[i]
            p = p.next
            lists[i] = lists[i].next
            if lists[i] :
                heappush(pq,(lists[i] .val,i))
        return dum.next

55 ms