Merge k Sorted Lists

Difficulty: Hard | Acceptance: 57.48% | Paid: No

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

• Examples
• Constraints
• Brute Force - Collect and Sort
• Optimal - Min-Heap/Priority Queue
• Divide and Conquer (Pairwise Merging)

Examples

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 list: 1->1->2->3->4->4->5->6

Input

lists = []

Output

[]

Input

lists = [[]]

Output

[]

Constraints

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length will not exceed 10^4.

Brute Force - Collect and Sort

Intuition

If we collect all elements from the k lists into an array, we can then sort it and recreate the merged list.

Steps

• Initialize an empty list to collect all node values.
• Traverse each linked list and add all node values to the collection.
• Sort the collection.
• Rebuild a new sorted linked list from the sorted values.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def mergeKLists_bruteforce(lists):
    if not lists:
        return None
    values = []
    for head in lists:
        current = head
        while current:
            values.append(current.val)
            current = current.next
    values.sort()
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

Complexity

• Time: O(N log N) where N is the total number of nodes across all lists. This is due to the sorting step.
• Space: O(N) for storing all node values and creating the new list.
• Notes: This approach is straightforward but not optimal. It doesn’t leverage the sorted nature of the individual lists.

Optimal - Min-Heap/Priority Queue

Intuition

Since each list is sorted, we can efficiently find the smallest element among all heads using a min-heap.

Steps

• Use a min-heap (priority queue) to keep track of the current smallest elements from each list.
• Initially, push the head of each non-empty list into the heap.
• Repeatedly extract the minimum element from the heap and append it to the result.
• If the extracted node has a next node, push the next node into the heap.
• Continue until the heap is empty.

import heapq
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists):
        # Initialize heap with the head of each list
        heap = []
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))
        
        # Dummy node to build the result
        dummy = ListNode(0)
        current = dummy
        
        # Process the heap
        while heap:
            val, i, node = heapq.heappop(heap)
            current.next = node
            current = current.next
            
            # If there's a next node, push it to the heap
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        
        return dummy.next

Complexity

• Time: O(N log k) where N is the total number of nodes across all lists and k is the number of lists. Each insertion and extraction from the heap takes O(log k) time, and we do this N times.
• Space: O(k) for the heap which can hold at most one node from each of the k lists.
• Notes: This is the optimal approach in terms of time complexity. It efficiently maintains the minimum element at each step. This approach is particularly efficient when k is much smaller than N.

Divide and Conquer (Pairwise Merging)

Intuition

We can reduce the problem by merging pairs of lists iteratively until we have a single list.

Steps

• If the list of lists is empty, return null.
• If there’s only one list, return it.
• While there’s more than one list, iterate through the list and merge pairs of adjacent lists.
• Replace the pairs with their merged result.
• Continue this process until only one list remains.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        current = dummy
        
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        
        current.next = list1 if list1 else list2
        return dummy.next
    
    def mergeKLists(self, lists):
        if not lists:
            return None
        
        while len(lists) > 1:
            merged_lists = []
            for i in range(0, len(lists), 2):
                list1 = lists[i]
                list2 = lists[i+1] if i+1 < len(lists) else None
                merged_lists.append(self.mergeTwoLists(list1, list2))
            lists = merged_lists
        
        return lists[0] if lists else None

Complexity

• Time: O(N log k) where N is the total number of nodes and k is the number of lists. We have log k levels of merging, and at each level, we process all N nodes.
• Space: O(1) if we don’t count the space used by the input. The merging process reuses existing nodes.
• Notes: This approach mirrors merge sort. It’s elegant and has the same time complexity as the heap-based approach but with constant space. It also has good cache performance due to sequential access patterns.