Merging Two Sorted Linked Lists

Defining the Problem

First, let's clearly define the task. You are given the heads of two singly linked lists, list1 and list2. Each list is guaranteed to be sorted in non-decreasing order. Your job is to merge them into a single sorted list by "splicing" together the nodes from the original two lists. This means you should rearrange the existing nodes' next pointers, not create a brand-new list with new nodes.

For example, if list1 is 5 -> 10 -> 15 and list2 is 2 -> 3 -> 20, the result should be 2 -> 3 -> 5 -> 10 -> 15 -> 20.

An Initial Thought: The Naive Approach

When faced with a new problem in an interview, it's often a good strategy to start by discussing a simple, even if suboptimal, solution. For this problem, one straightforward idea is to traverse both linked lists, collect all node values into an array, sort that array, and then build a new linked list from the sorted values.

This approach works, but it has significant drawbacks. Let's analyze its complexity. If the lists have lengths m and n, creating the array takes $O(m+n)$ time. Sorting this array takes $O((m+n)\log (m+n))$ time. Finally, creating a new list from the array takes another $O(m+n)$ time. The dominant factor is sorting, so the total time complexity is $O((m+n)\log (m+n))$. Furthermore, it requires $O(m+n)$ extra space for the array.

We can do much better. Since the lists are already sorted, we can leverage that property to build the merged list in a single pass, avoiding the need for a separate sorting step and extra storage.

The Optimal Iterative Solution

The most efficient approach is an iterative one that builds the merged list in place. The core idea is to maintain pointers to the current nodes in both list1 and list2 and, at each step, append the smaller of the two nodes to our result list.

A key technique here is the use of a dummy node. This is a placeholder node that acts as a temporary head for our new list. It elegantly solves the "empty list" edge case, as we always have a node to which we can append the first element. We'll also use a tail pointer, which always points to the last node in our merged list, making it easy to append the next node.

The NeetCode video below provides an excellent visual walkthrough of this exact process.

The algorithm can be summarized as follows:

1. Create a dummy node to serve as the start of the result list. Initialize a tail pointer to this dummy node.
2. While both list1 and list2 have nodes:
   • Compare the values of the current nodes of list1 and list2.
   • Set tail.next to point to the node with the smaller value.
   • Advance the pointer of the list from which you just took the node.
   • Advance the tail pointer to the new last node (tail = tail.next).
3. Once the loop finishes, one of the lists will be empty, but the other might still contain nodes. Since that remaining list is already sorted, we can simply append it to the end of our result by setting tail.next to the head of the remaining list.
4. Finally, return dummy.next, which is the true head of the merged, sorted list.

Let's see how this translates into clean, efficient Python code.

This iterative approach has a time complexity of $O(m+n)$ because we visit each node in both lists exactly once. Crucially, its space complexity is $O(1)$ because we are only using a few pointers (dummy, tail) and not allocating any new data structures proportional to the input size. This is the optimal solution and the one you should aim for in an interview.

The Recursive Solution

Another elegant way to think about this problem is through recursion. The problem exhibits a self-similar structure: merging two lists is equivalent to picking the smaller of the two head nodes and then merging the rest of the lists. This naturally lends itself to a recursive definition.

The logic is as follows:

• Base Case: If either list1 or list2 is empty, there's nothing to merge. Simply return the non-empty list.
• Recursive Step: Compare the values at the heads of list1 and list2.
  • If list1.val is smaller, then we know list1's head is the head of our merged list. Its next element will be the result of merging the rest of list1 (list1.next) with all of list2.
  • Otherwise, list2's head is the head of our merged list. Its next element will be the result of merging all of list1 with the rest of list2 (list2.next).

To get an even deeper understanding of how the program executes these recursive calls, the following video provides a step-by-step visualization of the call stack.

Complexity and Trade-offs

The recursive solution is concise and can be very intuitive once you grasp the pattern. However, it comes with a trade-off.

• Time Complexity: $O(m+n)$. Similar to the iterative solution, we process each node once.
• Space Complexity: $O(m+n)$. This is the key difference. Each recursive call adds a frame to the call stack. In the worst case, the depth of the recursion can be the sum of the lengths of the two lists, leading to space usage proportional to the input size. For very long lists, this could even lead to a stack overflow error.

Given your background as a full-stack developer, this is a classic trade-off: the iterative solution is generally preferred for production systems due to its $O(1)$ space complexity and robustness against stack limits, while the recursive solution is a beautiful demonstration of algorithmic thinking that is also important to know for interviews.

Conclusion

In this lesson, we explored two effective methods for merging sorted linked lists, a foundational problem in data structures. You've seen how to leverage the sorted property of the lists to achieve a linear time solution.

Key Takeaways:

• Problem: Merge two sorted linked lists into one by splicing existing nodes.
• Iterative Solution:
  • Uses a dummy node and a tail pointer to build the list.
  • Time Complexity: $O(m+n)$
  • Space Complexity: $O(1)$ - This is the optimal solution in terms of memory.
• Recursive Solution:
  • Defines the problem in terms of itself: pick the smaller head and recursively merge the rest.
  • Time Complexity: $O(m+n)$
  • Space Complexity: $O(m+n)$ due to the call stack.
• Trade-off: The iterative approach is more space-efficient and robust for large inputs, while the recursive approach can offer more concise code.

Having mastered fundamental linked list operations and patterns like fast/slow pointers and merging, we are now ready to move on. In the next lesson, we will shift our focus to another essential linear data structure: the stack. We will learn about its Last-In, First-Out (LIFO) principle and apply it to solve problems like validating parentheses.