Skip to content

23. Merge K Sorted Lists

Linked List Divide and Conquer Heap (Priority Queue) Merge Sort

Problem - Merge K Sorted Lists

Hard

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 linked 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.

Solutions

 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[Optional[ListNode]]) -> Optional[ListNode]:
        # Need to att a comparison method for the heap
        # to avoid TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'
        # lt is less than (<)
        setattr(ListNode, '__lt__', lambda a, b: a.val < b.val)
        heap = [head for head in lists if head]

        heapify(heap)
        pointer = current = ListNode()
        while heap:
            node = heappop(heap)
            if node.next:
                heappush(heap, node.next)
            current.next = node
            current = current.next
        return pointer.next

Submission Stats:

  • Runtime: 11 ms (59.07%)
  • Memory: 20.1 MB (69.86%)