23. 合并K个升序链表

难度困难1151

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：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：

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

示例 3：

1
2
输入：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. 优先队列

    heapq是二叉堆，通常用普通列表实现。

    heapq模块是在Python中不错的优先级队列实现。由于heapq在技术上只提供最小堆实现，因此必须添加额外步骤来确保排序稳定性，以此来获得“实际”的优先级队列中所含有的预期特性。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import heapq

    q = []

    heapq.heappush(q, (2, 'code'))
    heapq.heappush(q, (1, 'eat'))
    heapq.heappush(q, (3, 'sleep'))

    while q:
        next_item = heapq.heappop(q)
        print(next_item)

    # 结果：
    #   (1, 'eat')
    #   (2, 'code')
    #   (3, 'sleep')

    queue.PriorityQueue这个优先级队列的实现在内部使用了heapq，时间和空间复杂度与heapq相同。

    区别在于PriorityQueue是同步的，提供了锁语义来支持多个并发的生产者和消费者。

    在不同情况下，锁语义可能会带来帮助，也可能会导致不必要的开销。不管哪种情况，你都可能更喜欢PriorityQueue提供的基于类的接口，而不是使用heapq提供的基于函数的接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from queue import PriorityQueue

q = PriorityQueue()

q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))

while not q.empty():
    next_item = q.get()
    print(next_item)

# 结果：
#   (1, 'eat')
#   (2, 'code')
#   (3, 'sleep')

其中PriorityQueue可以自定义比较函数:

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
from queue import PriorityQueue
class Job(object):
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description
        print('New job:', description)
        return
 
    def __lt__(self, other):
        return self.priority < other.priority
 	''' 或者使用__cmp__函数
    def __cmp__(self, other):
        if self.priority < other.priority:
            return -1
        elif self.priority == other.priority:
            return 0
        else:
            return 1
    '''
q2 = PriorityQueue()
 
q2.put(Job(5, 'Mid-level job'))
q2.put(Job(10, 'Low-level job'))
q2.put(Job(1, 'Important job')) #数字越小，优先级越高
 
while not q2.empty():
    next_job = q2.get() #可根据优先级取序列
    print('Processing job', next_job.description)

题解:

使用heapq解决该问题，每一个链表的第一个节点进入堆进行比较，然后最小的那个取出来扔进新链表，然后最小的那个向后移动一位（80ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        minheap=[]
        for index,node in enumerate(lists):
            if node!=None:
                heapq.heappush(minheap,(node.val,index)) #第几个链表的节点的值

        head=ListNode(-1)
        tail=head
        while minheap:
            nodeval,index=heapq.heappop(minheap)
            tail.next=lists[index]
            tail=tail.next
            lists[index]=lists[index].next
            if lists[index]!=None:
                heapq.heappush(minheap,(lists[index].val,index))
        return head.next

使用PriorityQueue解决问题，速度慢于heapq(144ms)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        from queue import PriorityQueue
        minheap=PriorityQueue()
        for index,node in enumerate(lists):
            if node!=None:
               minheap.put((node.val,index)) #第几个链表的节点的值
        head=ListNode(-1)
        tail=head
        while not minheap.empty():
            nodeval,index=minheap.get()
            tail.next=lists[index]
            tail=tail.next
            lists[index]=lists[index].next
            if lists[index]!=None:
                minheap.put((lists[index].val,index))
        return head.next

  1. 分治

    首先实现合并两个链表，然后分治：

    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
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        # 合并两个链表的代码
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            if l1 and l2:
                if l1.val > l2.val:
                    l1,l2=l2,l1
                l1.next=self.mergeTwoLists(l1.next,l2)
            return l1 or l2
        #调用上面的代码合并两个节点
        def mergetwonode(self,node1:ListNode,node2:ListNode)->ListNode:
            return self.mergeTwoLists(node1,node2)
        #分治
        def merge(self,left:int,right:int,lists:List[ListNode])->ListNode:
            if left==right:
                return lists[left]
            if left>right:
                return None
            mid=left+((right-left)//2)
            return self.mergetwonode(self.merge(left,mid,lists),self.merge(mid+1,right,lists))        

        def mergeKLists(self, lists: List[ListNode]) -> ListNode:
            if not lists:
                return None
            return self.merge(0,len(lists)-1,lists)