Merge k Sorted Lists — LeetCode 23 Python Solution

The problem

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

Input

lists = [[1,4,5],[1,3,4],[2,6]]

Output

[1,1,2,3,4,4,5,6]

Explanation

The linked-lists are:

Python solution

# 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]:
        setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)
        pq = [head for head in lists if head]
        heapify(pq)
        dummy = cur = ListNode()
        while pq:
            node = heappop(pq)
            if node.next:
                heappush(pq, node.next)
            cur.next = node
            cur = cur.next
        return dummy.next

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 23. Merge k Sorted Lists is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems