Merge K Sorted Linked Lists [Solution]

Solution 1 (using a min-heap)

Here’s a Python implementation of the merge_k_sorted_lists function using a min-heap:

import heapq
from typing import List

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

def merge_k_sorted_lists(lists: List[ListNode]) -> ListNode:
    # Create a min-heap to store the elements along with their indices (value, index, node)
    min_heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(min_heap)

    # Create a dummy node to build the merged sorted list
    dummy = ListNode()
    current = dummy

    while min_heap:
        val, i, node = heapq.heappop(min_heap)
        current.next = node
        current = current.next

        # Move to the next node in the same list
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))

    return dummy.next

# Example usage:
# Create sorted linked lists: 1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))

result = merge_k_sorted_lists([list1, list2, list3])

# Display the merged sorted list: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
while result:
    print(result.val, end=" -> ")
    result = result.next
print("None")

This solution uses a min-heap to efficiently select the smallest element among the heads of the linked lists. We iteratively pop the smallest element from the heap, append it to the merged list, and move the corresponding list’s head to the next node.

Time Complexity:

The time complexity is O(N * log(k)), where N is the total number of elements in all linked lists, and k is the number of linked lists.

Space Complexity:

The space complexity is O(k) due to the min-heap.

Solution 2 (without using a heap)

Here’s a Python implementation of the merge_k_sorted_lists function without using a heap:

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

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 or l2

    return dummy.next

def merge_k_sorted_lists(lists: List[ListNode]) -> ListNode:
    if not lists:
        return None

    while len(lists) > 1:
        merged_lists = []

        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i + 1] if i + 1 < len(lists) else None
            merged_lists.append(merge_two_lists(l1, l2))

        lists = merged_lists

    return lists[0] if lists else None

# Example usage:
# Create linked lists: 1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))

result = merge_k_sorted_lists([list1, list2, list3])

# Display the merged sorted list: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
current = result
while current:
    print(current.val, end=" -> ")
    current = current.next
print("None")

In this solution, we repeatedly merge pairs of linked lists until only one linked list remains. The merge_two_lists function is used to merge two sorted linked lists.

Time Complexity:

The time complexity is O(N * log(k)), where N is the total number of nodes in all linked lists, and k is the number of linked lists.

Here’s a breakdown of the time complexity:

1. Merging Pairs Logarithmically:
   • In each iteration, we merge pairs of linked lists.
   • In the first iteration, we merge k/2 pairs, in the second iteration, k/4 pairs, and so on.
   • The number of iterations required to reduce k to 1 is log(k) due to the logarithmic nature of the merging process.
2. Merging Two Lists:
   • The merge_two_lists function takes O(N) time, where N is the total number of nodes in the two lists being merged.
   • In the worst case, we have to merge all nodes in a single iteration, resulting in O(N) time complexity for each merge operation.
3. Total Time Complexity:
   • The total number of merge operations is proportional to the logarithm of the number of linked lists, which is log(k).
   • Each merge operation takes O(N) time.
   • Therefore, the overall time complexity is O(N * log(k)).

It’s important to note that this time complexity is an improvement over a naive approach that would involve merging all linked lists one by one, resulting in a time complexity of O(N * k). The provided solution exploits the sorted order of the input lists to efficiently merge them logarithmically.

Space Complexity:

The space complexity is O(1).