LeetCode 23 - Merge k Sorted Lists

Question:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

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

Example 3:

Input: lists = [[]]

Output: []

Answer:

Here the goal is to combine all these lists into a single list that is still sorted in ascending order.

Divide and Conquer Approach:

To tackle this problem, think of it like sorting a big pile of cards.
It's easier if you divide the cards into smaller piles, sort those, and then combine them.
Similarly, we break the problem into smaller parts.

Then, we merge those sorted pairs into larger sorted groups, until we have just one fully sorted list.

Approach:

The mergeKLists function calls a recursive helper function mergeSort to divide and conquer the merging process.
The mergeSort function recursively divides the list of linked lists into smaller sublists until each sublist contains only one or zero linked lists.
The merge function is used to merge two sorted linked lists into one sorted linked list.

Why Merge Sort is Useful and Important:

Reliable Sorting: Merge Sort guarantees a time complexity of O(n log n) for worst, average, and best cases. This makes it efficient for large datasets.
Stable Sorting: It preserves the order of equal elements, which can be crucial in certain applications.
Predictable Performance: Merge Sort's consistent time complexity makes it a reliable choice regardless of input distribution.
Divide and Conquer: The algorithm's approach of breaking down a problem into smaller, more manageable subproblems can be applied to various other scenarios.
Parallelism: Merge Sort's divide-and-conquer nature allows for easy parallelization, making use of multiple processors or cores.
External Sorting: Merge Sort is suitable for sorting data that doesn't fit entirely in memory, making it ideal for external storage or distributed systems.
Learning Tool: Merge Sort is often taught as a foundational sorting algorithm, helping learners grasp key concepts like recursion, divide and conquer, and merging.
Merge Operation: The merging step, used in Merge Sort, is a fundamental operation in various algorithms beyond sorting.
Merge Sort Variants: Merge Sort has inspired variants and adaptations, such as Tim Sort used in Python's sorted function.

Time complexity:

The time complexity is O(N * log k), where N is the total number of nodes across all linked lists, and k is the number of linked lists. This is because in each merge step, the code compares and merges nodes, and there are log k levels of recursion, with each level performing O(N) comparisons.

Space complexity:

The merge function uses constant extra space.

The mergeSort function uses O(log k) extra space due to the recursive call stack.

Thus, the overall space complexity is O(log k).

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[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(l, r):
            res = ListNode(-float('inf'))
            ret = res
            while l and r:
                if l.val < r.val:
                    res.next = l
                    res = res.next
                    l = l.next
                else:
                    res.next = r
                    res = res.next
                    r = r.next
            while l:
                res.next = l
                res = res.next
                l = l.next
            while r:
                res.next = r
                res = res.next
                r = r.next
            return ret.next
        def mergeSort(lists,s,e):
            if s == e:
                return lists[s]
            mid = s+(e-s)//2
            l = mergeSort(lists,s,mid)
            r = mergeSort(lists,mid+1,e)
            return merge(l,r)
        if not lists:
            return None
        return mergeSort(lists,0,len(lists)-1)