23. Merge k Sorted Lists

23. Merge k Sorted Lists#

Difficulty: Hard

Link to Problem: To see the Merge k Sorted Lists problem on LeetCode, click here!

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.

Constraints:

k == lists.length
0 <= k <= \(10^4\)
0 <= lists[i].length <= 500
\(-10^4\) <= lists[i][j] <= \(10^4\)
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed \(10^4\).

# 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: [[ListNode]]) -> ListNode:
        # Check if the input list of linked lists is empty
        if not lists or len(lists) == 0:
            return None

        # Loop until there is only one merged list left
        while len(lists) > 1:
            mergedLists = []

            # Merge pairs of lists
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if (i + 1) < len(lists) else None
                mergedLists.append(self.mergeList(l1, l2))

            # Update the list of lists with merged results
            lists = mergedLists
        
        # Return the final merged list
        return lists[0]

    def mergeList(self, l1, l2):
        # Create a dummy node to simplify merging
        dummy = ListNode()
        tail = dummy

        # Merge the two sorted lists
        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

        # Append any remaining elements from l1 or l2 (if any)
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2

        # Return the merged result starting from the next of the dummy node
        return dummy.next

Explanation:#

The provided code defines a Python class Solution with two methods for merging k sorted linked lists:

mergeKLists(self, lists: List[ListNode]) -> ListNode: This method takes a list of k sorted linked lists as input and returns a single merged sorted linked list. It uses a divide-and-conquer approach to repeatedly merge pairs of lists until only one merged list remains.
mergeList(self, l1, l2): This method takes two sorted linked lists, l1 and l2, as input and merges them into a single sorted linked list. It uses a dummy node to simplify the merging process.

Here’s a high-level overview of how the code works:

The mergeKLists method checks if the input list of linked lists is empty or contains no lists. If there are no lists, it returns None.
Inside a while loop, the code repeatedly merges pairs of linked lists until only one merged list remains in the lists array. It does this by iterating through the input lists in pairs and calling the mergeList method to merge each pair.
The mergeList method takes two sorted linked lists, l1 and l2, and merges them into a single sorted linked list. It uses a dummy node (dummy) and a tail pointer to keep track of the merged list while comparing and merging elements from l1 and l2.
After merging all pairs of lists and updating the lists array with the merged results, the loop continues until only one merged list remains in the lists array.
Finally, the mergeKLists method returns the merged list.

Overall, this code efficiently merges k sorted linked lists using a divide-and-conquer strategy, resulting in a single merged sorted linked list as the output.

Test cases#

### Example 1
# Input: lists = [[1,4,5],[1,3,4],[2,6]]

lists1 = [
    ListNode(1, ListNode(4, ListNode(5))),
    ListNode(1, ListNode(3, ListNode(4))),
    ListNode(2, ListNode(6))
]
solution = Solution()
result1 = solution.mergeKLists(lists1)

# Print the result
if result1:
    current = result1
    while current:
        print(current.val, end=" -> ")
        current = current.next
else:
    print("None")  # Print "None" for input with a single None element

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 ->

### Example 2
# Input: lists = []

lists2 = []
solution = Solution()
result2 = solution.mergeKLists(lists2)

# Print the result
if result2:
    current = result2
    while current:
        print(current.val, end=" -> ")
        current = current.next
else:
    print("None")  # Print "None" for input with a single None element

None

### Example 3
# Input: lists = [[]]

lists3 = [None]
solution = Solution()
result3 = solution.mergeKLists(lists3)

# Print the result
if result3:
    current = result3
    while current:
        print(current.val, end=" -> ")
        current = current.next
else:
    print("None")  # Print "None" for input with a single None element

None

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

Heap Initialization: The code does not use a heap. Instead, it uses a divide-and-conquer approach. The initial check for empty input lists takes \(O(1)\) time.
Merging: The merging operation is performed in a divide-and-conquer fashion. In each iteration of the while loop, we merge pairs of linked lists, and the number of comparisons made is proportional to the total number of nodes across all the linked lists (\(n\)). In each merge step, we effectively process each node once. The number of iterations required to reduce k lists to 1 is \(O(log\ k)\).

Therefore, the overall time complexity of the code is \(O(n * log\ k)\), where n is the total number of nodes across all lists, and \(k\) is the number of linked lists.

Space Complexity:

Heap Space: The code doesn’t use a heap data structure, so there’s no additional space complexity due to a heap.
Merged Lists: In the mergeList method, we create a new merged list. However, this list is not stored in memory for all lists; it’s replaced with each merged pair. The space used for these merged lists is proportional to the size of the largest merged list, which is \(O(n)\) in the worst case.
Additional Variables: The code uses a few additional variables, such as dummy and tail, but these occupy a constant amount of space and don’t depend on the input size.

Therefore, the overall space complexity of the code is \(O(n)\), where n is the total number of nodes across all lists.

In summary, the code’s time complexity is \(O(n * log(k))\), and its space complexity is \(O(n)\). This code efficiently merges \(k\) sorted linked lists using a divide-and-conquer approach with a relatively low space overhead.

23. Merge k Sorted Lists

Contents

23. Merge k Sorted Lists#

Explanation:#

Test cases#