Leetcode: 23. Merge k Sorted Lists

Problem Statement

Understand the problem

Given an array of sorted linked lists, return a linked list that contains all elements sorted.

Devise a plan

Use a sorted list to store the head of each list, pick the smallest one and add to the end of the answer. If the list has a next element, add it back to the sorted list. Time complexity is \(O(n \log n)\) and space is \(O(1)\).

Carry out the plan

# 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]:
        pq = []
        for i, l in enumerate(lists):
            if l:
                heappush(pq, (l.val, i))
        head = None
        tail = None
        while pq:
            _, i = heappop(pq)
            if head is None:
                head = tail = lists[i]
            else:
                tail.next = tail = lists[i]
            lists[i] = lists[i].next
            if lists[i]:
                heappush(pq, (lists[i].val, i))
        return head

Common mistakes

Cited by 2