Merge k Sorted Lists - Python Solution

1. Introduction

"Merging k Sorted Lists" is a more advanced problem in the domain of linked lists, expanding upon the concept of merging two sorted lists. This problem involves combining multiple sorted linked lists into a single sorted list, demonstrating efficient ways to handle multiple data streams. It's a common challenge in algorithm design, particularly in scenarios like merging logs from multiple sources or combining sorted data from different databases.

Problem

Given an array of k linked-lists lists, with each linked-list sorted in ascending order, the task is to merge all the linked-lists into one sorted linked-list and return it.

2. Solution Steps

1. Initialize a min-heap to efficiently retrieve the smallest node among the heads of the k lists.

2. Add the first node of each list to the heap.

3. While the heap is not empty, extract the smallest node from the heap.

4. Append the extracted node to the merged list and move its pointer to the next node in its respective list.

5. If the next node exists, add it to the heap.

6. Continue this process until all nodes from all lists are processed.

7. Return the head of the merged list.

3. Code Program

import heapq

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

def mergeKLists(lists):
    dummy = ListNode()
    current = dummy
    heap = []

    for l in lists:
        if l:
            heapq.heappush(heap, (l.val, l))

    while heap:
        val, node = heapq.heappop(heap)
        current.next = ListNode(val)
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))

    return dummy.next

# Example Usage
# Creating lists for demonstration
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))
result = mergeKLists([list1, list2, list3])
# Output the list
output = []
while result:
    output.append(result.val)
    result = result.next
print(output)

Output:

[1, 1, 2, 3, 4, 4, 5, 6]

Explanation:

1. ListNode Class: ListNode class is used for representing each node in the linked lists.

2. Min-Heap for Efficiency: A min-heap is used to quickly find the smallest current node among the heads of the lists.

3. Merging Process: Nodes are popped from the heap and added to the merged list, maintaining sorted order.

4. Heap Update: After adding a node to the merged list, its next node is pushed to the heap if it exists.

5. Iterative Approach: The process repeats until all nodes from all lists are merged.

6. Result: The function returns a new sorted linked list formed by merging all the k sorted linked lists.

7. Efficient and Scalable: This solution efficiently merges multiple lists and is scalable for a large number of lists.