Merge k Sorted Lists hard

Problem Statement

Merge k sorted linked lists into one sorted linked list.

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: []

Steps

1. Handle Empty Input: If the input list lists is empty, return an empty list.

2. Choose a Merge Strategy: We'll use a divide-and-conquer approach combined with a merge-two-sorted-lists helper function. This is more efficient than other approaches like repeatedly merging two lists at a time.

3. Divide and Conquer: Recursively merge pairs of lists until only one list remains.

4. Merge Two Sorted Lists: A helper function will efficiently merge two sorted linked lists.

5. Return the Result: The final merged list is returned.

Explanation

The core idea is to recursively merge sub-problems. Imagine merging four sorted lists (A, B, C, D). We can merge A and B, C and D separately, then merge the results of these merges. This reduces the problem to merging smaller sets of lists. The base case is when we have just one list, which is already sorted.

The mergeTwoLists function is a standard merge operation similar to merging two sorted arrays. It iteratively compares the heads of the two lists and adds the smaller node to the merged list.

Code

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        if not lists:
            return None

        def mergeTwoLists(l1, l2):
            dummy = ListNode()  # Dummy node to simplify the head insertion
            tail = dummy
            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  # Attach the remaining list
            return dummy.next

        while len(lists) > 1:
            mergedLists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                mergedLists.append(mergeTwoLists(l1, l2))
            lists = mergedLists
        return lists[0] if lists else None



# Example Usage
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))

solution = Solution()
merged_list = solution.mergeKLists([list1, list2, list3])

result = []
while merged_list:
    result.append(merged_list.val)
    merged_list = merged_list.next

print(result)  # Output: [1, 1, 2, 3, 4, 4, 5, 6]

Complexity

• Time Complexity: O(N log k), where k is the number of linked lists and N is the total number of nodes. The merge operation in mergeTwoLists is O(N) for each merge level and we have at most log k levels of merge operations in our divide and conquer approach.

• Space Complexity: O(1) in-place merging (excluding the space for the result list itself, which is O(N)) if we consider recursive call stack space as constant. If we consider the space used by recursive calls, then it is O(log k) because of the recursion depth in divide and conquer. We only use a constant amount of extra space during the merge operations.