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 you get a time complexity of $O(nlog(n))$. Which is a significant improvement from $O(n^2)$.

Solution in Python


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]:
        # edge case
        if len(lists) == 0:
            return None

        # while there are lists to merge, keep merging
        while len(lists) > 1:
            # this will hold merged lists
            tempList = []
            # we merge in steps of 2
            # for example, index 0 and 1 are merged,
            # then the next indices we merge are 2 and 3
            for i in range(0, len(lists), 2):
                # if there's an index after this one, we merge
                if i + 1 < len(lists):
                    # merge 2 lists
                    v = self.merge2Lists(lists[i], lists[i + 1])
                    # if the new head exists, add it else skip
                    if v is not None:
                        tempList.append(v)
                # else we can't merge this index with anything, so add it as is
                else:
                    tempList.append(lists[i])
            # our next iteration needs to merge these merged lists
            lists = tempList

        # if there's a final merged list, return that, otherwise just return an empty list
        return lists[0] if len(lists) is not 0 else []

    # helper function to merge 2 linked lists and return the new head
    def merge2Lists(self, l1: ListNode, l2: ListNode) -> ListNode | None:
        # edge cases
        # if both lists are empty, return empty
        if l1 is None and l2 is None:
            return None
        # is list 1 is empty, then list 2 should be returned
        elif l1 is None:
            return l2
        # is list 2 is empty, then list 1 should be returned
        elif l2 is None:
            return l1

        # pointers p1 and p2 for list 1 and list 2 respectively
        p1 = l1
        p2 = l2

        # this will serve as the head of the merged list
        p3 = None

        # this little bit decides which list's first element becomes the head of the merged list
        if p1.val < p2.val:
            p3 = p1
            p1 = p1.next
        else:
            p3 = p2
            p2 = p2.next

        head = p3

        # while both lists have elements in them, keep merging
        while p1 is not None and p2 is not None:
            if p1.val < p2.val:
                p3.next = p1
                p1 = p1.next
            else:
                p3.next = p2
                p2 = p2.next

            p3 = p3.next

        # now either only l1 or l2 has elements in it
        # all we need to do is append it to the merged list

        # if l1 has elements left, but l2 does not
        # just dump the remaining contents of l1 into the merged list
        while p1 is not None:
            p3.next = p1
            p1 = p1.next
            p3 = p3.next

        # if l2 has elements left, but l1 does not
        # just dump the remaining contents of l2 into the merged list
        while p2 is not None:
            p3.next = p2
            p2 = p2.next
            p3 = p3.next

        # return the head of the merged list
        return head

Complexity

  • Time: $O(nlog(n))$

  • Space: $O()$

Mistakes I Made

As I said, I tried to brute force it.

And we are done.