Merge K Sorted Lists 🎯

Welcome to an exciting journey through the world of data structures and algorithms! Today, we're going to learn how to merge K sorted lists. This technique is incredibly useful in various real-world applications, such as databases, search engines, and more.

Understanding the Problem 📝

Given K sorted linked lists, we need to merge them into one sorted list. This problem is a great example of how to implement a priority queue (min-heap) using a linked list.

Merging Two Sorted Lists 💡

Let's start by merging two sorted lists. We'll use a dummy head node to simplify the process.

python

def mergeTwoLists(list1, list2):
    # Initialize dummy head node
    dummy = ListNode(0)
    tail = dummy

    # Continue until either list1 or list2 has no remaining nodes
    while list1 and list2:
        # Check which node has the smaller value
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        # Move the tail to the end of the merged list
        tail = tail.next

    # If there are remaining nodes in either list, append them to the merged list
    tail.next = list1 or list2

    return dummy.next

📝 Note: In the above code, ListNode is a custom class representing a node in the linked list.

Merging K Sorted Lists 💡

Now that we've merged two sorted lists, let's extend this technique to merge K sorted lists. We can do this by using a priority queue to maintain the smallest nodes from each list.

python

from heapq import heappush, heappop

def mergeKSortedLists(lists):
    # Initialize min-heap and dummy head node
    heap = []
    dummy = ListNode(0)
    tail = dummy

    # Add the head nodes of all the lists to the heap
    for list in lists:
        if list:
            heappush(heap, (list.val, list))

    # Continue until the heap is empty
    while heap:
        # Get the smallest value and its corresponding list node
        val, list_node = heappop(heap)

        # Add the node to the merged list
        tail.next = list_node
        tail = tail.next

        # Move to the next node in the list
        list_node = list_node.next

        # If the next node exists, add it to the heap if it's smaller than the current smallest value
        if list_node:
            heappush(heap, (list_node.val, list_node))

    return dummy.next

Practical Application 💡

Merging K sorted lists can be used in various real-world scenarios, such as:

Database management systems for merging multiple sorted result sets
Search engines for combining multiple sorted lists of search results
Graph algorithms like Dijkstra's shortest path algorithm where we have multiple priority queues (min-heaps) representing the vertices

Merge K Sorted Lists 🎯

Merge K Sorted Lists 🎯

Understanding the Problem 📝

Merging Two Sorted Lists 💡

Merging K Sorted Lists 💡

Practical Application 💡

Quiz 🎯