LeetCode Solutions Blog

Merge k Sorted Lists

Number: 23

Difficulty: Hard

Paid? No

Problem Description

Given an array of k sorted linked lists, merge them into one sorted linked list and return its head. Each individual list is sorted in ascending order.

Key Insights

Use a min-heap (priority queue) to efficiently extract the smallest value among the current heads of the lists.
By pushing the head of each non-empty list into the heap, we can pull the smallest node, then push that node’s next element into the heap.
Alternatively, a divide and conquer approach can be used by recursively merging pairs of lists.
Careful management of pointers (or references) is key to constructing the new linked list.

Space and Time Complexity

Time Complexity: O(N log k) where N is the total number of nodes across all lists and k is the number of lists. Space Complexity: O(k) due to the heap containing at most one node from each list.

Solution

We use a min-heap to always retrieve the smallest node among the current nodes in the linked lists. First, initialize the heap with the head of each list. Then, continuously extract the smallest node from the heap, attach it to the merged list, and if the extracted node has a next node, insert that into the heap. The process repeats until the heap is empty.

Code Solutions

# 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):
        # Create a min-heap
        min_heap = []
        # Heap entry: (node value, unique id, node) to handle duplicate values
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(min_heap, (node.val, i, node))
        
        # Dummy node to form the start of merged list
        dummy = ListNode(0)
        current = dummy
        
        # While there are elements in the heap
        while min_heap:
            # Pop the smallest node from the heap
            val, idx, node = heapq.heappop(min_heap)
            # Add the smallest node to the merged list
            current.next = node
            current = current.next
            # If there is a next node in the list, push it into the heap
            if node.next:
                heapq.heappush(min_heap, (node.next.val, idx, node.next))
        
        return dummy.next