Problem Statement

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.

Additional information

• 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.

Example 1:

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

Example 2:

Input: lists = []

Output: []

Example 3:

Input: lists = [[]]

Output: []

Brute Force (Collect & Sort)

Intuition

The simplest way to solve this is to ignore the fact that the individual lists are already sorted. We can just traverse every single linked list, extract all the node values into a giant array, sort that array, and then build a brand new linked list from the sorted values.

Algorithm

1. Initialize an empty array nodes.
2. Iterate through each linked list in lists.
3. For each linked list, traverse its nodes and append their values to the nodes array.
4. Sort the nodes array in ascending order.
5. Create a dummy node to build the new linked list.
6. Iterate through the sorted nodes array, creating a new ListNode for each value and attaching it to the dummy chain.
7. Return dummy.next.

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    nodes = []
    
    for l in lists:
        curr = l
        while curr:
            nodes.append(curr.val)
            curr = curr.next
            
    nodes.sort()
    
    dummy = ListNode(0)
    curr = dummy
    for val in nodes:
        curr.next = ListNode(val)
        curr = curr.next
        
    return dummy.next

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Extracting values takes O(N), where N is the total number of nodes across all lists. Sorting them takes O(N log N). Creating the new list takes O(N).

• Space complexity: O(N)

• Reason: We store all N values in an array and create a completely new linked list of size N.

Min-Heap / Priority Queue (Optimal)

Intuition

Since each individual list is already sorted, the smallest overall element must be the head of one of the k lists.

We can use a Min-Heap to efficiently find the minimum element among the k heads. We push the head of each list into the heap. Then, we repeatedly pop the smallest node from the heap, add it to our result list, and push the next node from that same list into the heap.

Algorithm

1. Import heapq. Create a min_heap.
2. Initialize a dummy node and a tail pointer for the result list.
3. Iterate through the lists. For each non-empty list, push a tuple (node.val, i, node) into the heap.
4. While the heap is not empty:

• Pop the smallest tuple from the heap to get the node.
• Attach this node to tail.next and move tail forward.
• If node.next exists, push (node.next.val, i, node.next) into the heap.

5. Return dummy.next.

import heapq

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    min_heap = []
    
    for i, l in enumerate(lists):
        if l:
            heapq.heappush(min_heap, (l.val, i, l))
            
    dummy = ListNode(0)
    tail = dummy
    
    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        tail.next = node
        tail = tail.next
        
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))
            
    return dummy.next

Time & Space Complexity

• Time complexity: O(N log k)

• Reason: There are N nodes in total. Each push/pop operation on a heap of size k takes O(log k) time.

• Space complexity: O(k)

• Reason: The min-heap contains at most k elements (one from each list) at any given time.