Problem Description

You need to merge two sorted linked lists into a single sorted linked list.

Given two linked lists list1 and list2, where each list is already sorted in ascending order, your task is to combine them into one linked list that maintains the sorted order.

The merging should be done by splicing the existing nodes together - meaning you should reuse the nodes from the original lists rather than creating new nodes. You simply need to rearrange the next pointers to connect the nodes in the correct order.

For example:

• If list1 is 1 -> 2 -> 4 and list2 is 1 -> 3 -> 4
• The merged result should be 1 -> 1 -> 2 -> 3 -> 4 -> 4

The function should return the head node of the newly merged linked list.

The solution uses a recursive approach:

1. If either list is empty, return the other list (base case)
2. Compare the values of the current heads of both lists
3. Choose the node with the smaller value as the next node in the merged list
4. Recursively merge the remainder of the chosen list with the other list
5. Connect the chosen node to the result of the recursive call

This approach ensures that at each step, we're always selecting the smaller value between the two current heads, maintaining the sorted order throughout the merging process.

Intuition

When merging two sorted lists, we need to repeatedly make a simple decision: which element should come next in our merged list? Since both lists are already sorted, we know the smallest remaining element must be one of the two current heads.

Think of it like merging two sorted piles of cards face-up. You can only see the top card of each pile, and you need to build a new sorted pile. The strategy is straightforward - always take the smaller top card and add it to your result pile.

The recursive nature becomes clear when we realize that after choosing one node, we're left with the same problem but slightly smaller - we still need to merge two sorted lists, just with one list having one fewer element. This self-similar structure naturally leads to recursion.

The key insight is that once we decide which node comes first (the one with the smaller value), the rest of the merged list is simply the result of merging:

• The remainder of the chosen list (everything after the head we just picked)
• The entirety of the other list (which still has its original head)

For example, if we have list1 = [1, 3, 5] and list2 = [2, 4, 6]:

• We compare 1 and 2, choose 1
• Now we need to merge [3, 5] with [2, 4, 6]
• This is the exact same problem, just smaller!

The base case emerges naturally: when one list becomes empty, there's nothing left to compare - we simply return the non-empty list as it's already sorted.

By connecting each chosen node to the result of merging the remaining elements, we build our final sorted list from the bottom up as the recursive calls return.

Learn more about Recursion and Linked List patterns.

Solution Approach

The solution implements a recursive approach to merge two sorted linked lists. Let's walk through the implementation step by step:

Base Case Handling:

if list1 is None or list2 is None:
    return list1 or list2

When either list1 or list2 is empty (None), we return the non-empty list. The expression list1 or list2 elegantly returns list1 if it's not None, otherwise returns list2. This handles three scenarios:

• If list1 is None, return list2
• If list2 is None, return list1
• If both are None, return None

Recursive Merging: The core logic compares the values at the heads of both lists:

if list1.val <= list2.val:
    list1.next = self.mergeTwoLists(list1.next, list2)
    return list1

When list1's head value is smaller or equal:

1. We choose list1's head as the next node in our merged list
2. Recursively merge list1.next (rest of list1) with the entire list2
3. Connect the result of the recursive call to list1.next
4. Return list1 as the head of the merged portion

else:
    list2.next = self.mergeTwoLists(list1, list2.next)
    return list2

When list2's head value is smaller:

1. We choose list2's head as the next node
2. Recursively merge the entire list1 with list2.next (rest of list2)
3. Connect the result to list2.next
4. Return list2 as the head of the merged portion

How the Recursion Builds the Result: The recursion works from the bottom up. Each recursive call:

1. Selects the smaller head node
2. Makes a recursive call to merge the remaining nodes
3. Connects the selected node to the result of the recursive call
4. Returns the selected node

As the recursion unwinds, it builds the complete merged list by connecting nodes in sorted order. The beauty of this approach is that we're reusing the existing nodes and only modifying their next pointers to create the merged structure.

Time and Space Complexity:

• Time: O(m + n) where m and n are the lengths of the two lists, as we visit each node exactly once
• Space: O(m + n) for the recursion call stack in the worst case

Example Walkthrough

Let's trace through merging list1 = 1 -> 3 -> 5 and list2 = 2 -> 4 step by step.

Initial Call: mergeTwoLists([1->3->5], [2->4])

• Compare heads: 1 < 2
• Choose node with value 1 from list1
• Make recursive call: mergeTwoLists([3->5], [2->4])

Second Call: mergeTwoLists([3->5], [2->4])

• Compare heads: 3 > 2
• Choose node with value 2 from list2
• Make recursive call: mergeTwoLists([3->5], [4])

Third Call: mergeTwoLists([3->5], [4])

• Compare heads: 3 < 4
• Choose node with value 3 from list1
• Make recursive call: mergeTwoLists([5], [4])

Fourth Call: mergeTwoLists([5], [4])

• Compare heads: 5 > 4
• Choose node with value 4 from list2
• Make recursive call: mergeTwoLists([5], [])

Fifth Call: mergeTwoLists([5], [])

• list2 is empty (base case)
• Return list1: [5]

Unwinding the Recursion:

As the recursive calls return, connections are made:

1. Fourth call returns: Node 4 connects to [5], becoming 4 -> 5
2. Third call returns: Node 3 connects to [4->5], becoming 3 -> 4 -> 5
3. Second call returns: Node 2 connects to [3->4->5], becoming 2 -> 3 -> 4 -> 5
4. Initial call returns: Node 1 connects to [2->3->4->5], becoming 1 -> 2 -> 3 -> 4 -> 5

Final Result: 1 -> 2 -> 3 -> 4 -> 5

The key insight is that each recursive call selects the smaller head, delegates the remaining merge to a recursive call, and then connects the selected node to the result. This builds the merged list from bottom to top as the recursion unwinds.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n)

The recursive solution visits each node from both linked lists exactly once. In each recursive call, we process one node from either list1 or list2 and make a recursive call with the remaining nodes. Since we have m nodes in list1 and n nodes in list2, the total number of recursive calls equals m + n. Each recursive call performs constant time operations (comparison and pointer assignment), resulting in an overall time complexity of O(m + n).

Space Complexity: O(m + n)

The space complexity is determined by the recursive call stack. In the worst case, we need to make m + n recursive calls before reaching the base case (when one or both lists become None). Each recursive call adds a new frame to the call stack, consuming O(1) space. Therefore, the maximum depth of the recursion is m + n, leading to a space complexity of O(m + n). This represents the implicit space used by the recursion stack rather than explicit auxiliary space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Stack Overflow with Very Long Lists

The recursive solution can cause a stack overflow when merging extremely long lists (typically lists with thousands of nodes), as each recursive call adds a frame to the call stack.

Why it happens: The recursion depth equals the total number of nodes in both lists. Python has a default recursion limit (usually around 1000), which can be exceeded with large inputs.

Solution: Use an iterative approach instead:

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # Create a dummy node to simplify the logic
    dummy = ListNode(0)
    current = dummy
  
    # Iterate while both lists have nodes
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
  
    # Attach any remaining nodes
    current.next = list1 or list2
  
    return dummy.next

2. Modifying Input Lists Without Consideration

The recursive solution modifies the original linked lists by changing their next pointers. This might be unexpected if the caller needs to preserve the original list structures.

Why it matters: After merging, the original lists are destroyed and cannot be used independently anymore.

Solution: If preserving original lists is required, create new nodes instead of reusing existing ones:

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    if not list1 or not list2:
        # Create copies of remaining nodes if needed
        return self.copyList(list1 or list2)
  
    if list1.val <= list2.val:
        new_node = ListNode(list1.val)
        new_node.next = self.mergeTwoLists(list1.next, list2)
        return new_node
    else:
        new_node = ListNode(list2.val)
        new_node.next = self.mergeTwoLists(list1, list2.next)
        return new_node

3. Not Handling Equal Values Consistently

While the current solution correctly handles equal values by using <=, beginners might use only <, which could lead to infinite recursion in certain edge cases or incorrect ordering when custom comparison logic is involved.

Why it matters: Using strict inequality (<) without proper else handling could cause issues with stability of the merge or create unexpected behavior.

Best Practice: Always use <= to ensure deterministic behavior and maintain stability (elements from list1 come before equal elements from list2).