Merge k Sorted Lists

Merge k Sorted Lists

January 6, 2024
medium
Divide and Conquer, Merge Sort

Problem #

You are given an array of k linked lists, each containing nodes of sorted integers. Merge all the linked lists into one sorted linked list and return its head.

Solution Approach #

  1. Divide: Recursively divide the list of lists into two halves until each sublist contains only one or zero lists.
  2. Conquer: Merge each pair of sublists using a merge function that combines two sorted lists into a single sorted list.
  3. Combine: Recurse up the call stack, merging the results of the sub-problems until the final sorted list is obtained.

Code (Python):

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

def mergeKLists(lists):
    """
    Merges k sorted linked lists into a single sorted linked list.

    Args:
        lists: A list of ListNode objects representing the sorted linked lists.

    Returns:
        The head of the merged sorted linked list.
    """

    def mergeTwoLists(l1, l2):
        """Merges two sorted linked lists."""
        dummy = tail = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

    if not lists:
        return None  # Handle empty input

    # Recursively divide and merge lists
    return mergeKLists(mergeTwoLists(lists[:len(lists) // 2], lists[len(lists) // 2:]))

Time Complexity #

O(N log k), where N is the total number of nodes in all lists, and k is the number of lists.

Space Complexity #

O(log k) for the recursion stack.