Problem Statement in English

You’re given a list of linked lists. The elements of each linked list are sorted in ascending order.

Your task is to merge all the linked lists into one sorted (in ascending order) linked list and return the head to that list.

Approach

The naive approach would be to just iterate over linked list in the main list, which would have a time complexity of $O(n^2)$. It’s basically iterating over a matrix at that point. This is the bruteforce approach.

Try this and you’ll get a TLE (Time Limit Exceeded). How do I know? I tried it. Hehe.

We need something smarter. Enter Merge Sort. That’s it.

    graph TD
    A((1,2,3,4)) --> B((1,2))
    A --> C((3,4))

    B --> D((1))
    B --> E((2))

    C --> F((3))
    C --> G((4))

Now, why is this better? It’s classic divide and conquer.

The recursion relation for this is given by: $2T(\frac{n}{2}) + O(n)$ , which is of the form $aT(\frac{n}{b})+ f(x)$, where:

  • a is the number of problems each stage is divided into
  • b is the size of each sub problem
  • f(x) is the cost of combining the solutions to 2 such problems

On solving this (it fits the Master Theorem) you get a time complexity of $O(nlog(n))$. Which is a nice improvement from $O(n^2)$.

From a code perspective, we can reuse the code for merging 2 sorted linked lists, which is a classic problem in itself. We can use that to merge 2 lists at a time, and keep doing that until we have only 1 list left.

And we’re done!

Solution in Python


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: 
        if not lists or len(lists) == 0:
            return None
        
        while len(lists) > 1:
            temp = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i+1] if i + 1 < len(lists) else None
                temp.append(self.merge_lists(l1, l2))
            lists = temp
        
        return lists[0]
    
    def merge_lists(self, l1, l2):
        node = ListNode()
        ans = node
        
        while l1 and l2:
            if l1.val > l2.val:
                node.next = l2
                l2 = l2.next
            else:
                node.next = l1
                l1 = l1.next
            node = node.next
        
        if l1:
            node.next = l1
        else:
            node.next = l2
        
        return ans.next

Complexity

  • Time: $O(nlog(n))$
    As was explained above, the time complexity is $O(nlog(n))$ due to the divide and conquer approach.

  • Space: $O(1)$
    Since we are not using any extra space, the space complexity is $O(1)$.

Mistakes I Made

As I said, I tried to brute force it.

And we are done.