LeetCode

Appearance

23. Merge k Sorted Lists ​

题目 ​

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

 

Constraints:

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 104.
Related Topics
  • 链表
  • 分治
  • 堆（优先队列）
  • 归并排序

  • 👍 3028
  • 👎 0

    • 思路 ​

    • 合并 linked list 时无法确定 head，需要使用 dummy head 模拟头节点
    • 采用 Priority Queue (Min-Heap) 进行所有 linked list 头节点排序
    • 注意 Priority Queue 不能对比对象，当遇到 Val 相同时会报错，需要使用 UID 进行辅助比较
    • 最小节点出队列后，最小节点的下一个节点进入对列，直到对列为空

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        k = len(lists)
        pq = []
        uid = 0  # Unique ID counter
        dummy = ListNode(0, None)
        cur = dummy
        for i in range(k):
            node = lists[i]
            if node:
                uid += 1
                heapq.heappush(pq,(node.val, uid, node))

        while pq:

            _, _, node = heapq.heappop(pq)
            cur.next = node
            cur = cur.next
            if node.next:
                uid += 1
                heapq.heappush(pq, (node.next.val, uid, node.next))

        return dummy.next




        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)