We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Merge k Sorted Lists

Difficulty: Hard

Problem Description

You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Key Insights

  • Each linked-list is already sorted, which allows us to efficiently merge them.
  • We can use a priority queue (min-heap) to always extract the smallest element among the heads of the k linked-lists.
  • Alternatively, we can use a divide and conquer approach to recursively merge pairs of linked-lists.

Space and Time Complexity

Time Complexity: O(N log k), where N is the total number of nodes across all linked-lists, and k is the number of linked-lists. Space Complexity: O(k) for the priority queue.

Solution

To solve this problem, we can use a min-heap (priority queue) to keep track of the smallest current node from each linked-list. The steps are as follows:

  1. Initialize a min-heap and add the head of each linked-list to the heap.
  2. Create a dummy node to simplify the merging process.
  3. Continuously extract the smallest node from the heap and add it to the merged list.
  4. If the extracted node has a next node, push that next node into the heap.
  5. Repeat until all nodes have been processed and return the merged list starting from the next of the dummy node.

Code Solutions

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    # Create a min-heap
    min_heap = []
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(min_heap, (lists[i].val, i, lists[i]))
    
    # Create a dummy node to facilitate the merged list
    dummy = ListNode(0)
    current = dummy
    
    while min_heap:
        # Get the smallest node
        val, idx, node = heapq.heappop(min_heap)
        current.next = ListNode(val)  # Add it to the merged list
        current = current.next
        
        # If there's a next node, push it onto the heap
        if node.next:
            heapq.heappush(min_heap, (node.next.val, idx, node.next))
    
    return dummy.next
← Back to All Questions