Merging Two Sorted Linked Lists

1. Brute-Force: The "Collect and Sort" Method

When first approaching this problem, the most direct solution is to leverage data structures you're already familiar with. Since the goal is a single sorted list, we can simply gather all the elements from both input lists, sort them, and then construct a new linked list from the sorted elements.

The steps for this approach are:

1. Create a dynamic array, like a Java ArrayList.
2. Traverse the first linked list (list1) and add each node's value to the array.
3. Traverse the second linked list (list2) and add each of its node's values to the same array.
4. Use a standard sorting function, such as Collections.sort(), to sort the array.
5. Create a new linked list by iterating through the sorted array and creating a new node for each element.

The following video from the takeUforward channel explains this brute-force strategy clearly.

To see this implemented in Java, you can review the corresponding section in the takeUforward article.

This method is functionally correct but has significant drawbacks in terms of efficiency, which an interviewer would immediately ask you to improve upon.

• Time Complexity: O(N log N), where N is the total number of nodes (N1 + N2). The dominant step is sorting the array.
• Space Complexity: O(N), as we need an array to store all N elements, plus the space for the newly created linked list.

The key inefficiency is that we are ignoring a critical piece of information: the input lists are already sorted. Our next approaches will exploit this property.

2. A Better Approach: Recursive Merging

A more elegant solution uses recursion, which often maps well to linked list problems due to their inherent recursive structure (a list is a head node followed by the rest of the list). The logic here follows a "divide and conquer" strategy.

The core idea is:

1. Base Cases: If either of the lists is empty, the result of the merge is simply the other, non-empty list.
2. Recursive Step: Compare the values at the heads of list1 and list2.
   • If list1.data is smaller, then this node is the head of our merged list. Its next pointer should be the result of recursively merging the rest of list1 (i.e., list1.next) with the entirety of list2.
   • Otherwise, list2.data is smaller (or equal), so it becomes the head. Its next pointer is the result of recursively merging list1 with the rest of list2 (list2.next).

This approach builds the final list by repeatedly picking the smaller of the two available nodes and letting recursion handle the rest. To visualize how the call stack manages this process, the following video provides an excellent, detailed walkthrough.

The GeeksforGeeks article below also provides a clear algorithm and Java implementation for this recursive method.

This approach is much more efficient time-wise, but it has a hidden space cost.

• Time Complexity: O(N1 + N2). We visit each node in both lists exactly once.
• Space Complexity: O(N1 + N2). This is due to the recursion call stack. In the worst-case scenario (e.g., merging a list with one very large element and another list with many small elements), the recursion depth can be equal to the total number of nodes.

This leads us to the optimal solution, which achieves the same time complexity but with constant space.

3. Optimal Approach: Iterative Two-Pointer Merge

The standard and most efficient solution for this problem is an iterative one that uses two pointers and a dummy node. This approach avoids the overhead of the recursion stack and manipulates the next pointers of the existing nodes directly, achieving O(1) space complexity.

Here’s the process:

1. Create a dummy node (e.g., with a value of -1). This acts as a sentinel, providing a fixed starting point for our new list and simplifying the code by removing edge cases for an empty list.
2. Create a tail pointer, initially pointing to the dummy node. This tail pointer will always point to the last node of the merged list as we build it.
3. Use two pointers, l1 and l2, to traverse the input lists.
4. While both l1 and l2 are not null, compare their values:
   • Whichever node is smaller is appended to the merged list by setting tail.next to that node.
   • The pointer of the list from which the node was taken is advanced (e.g., l1 = l1.next).
   • The tail pointer is advanced to the newly added node (tail = tail.next).
5. When the loop terminates, one of the lists is exhausted. The other list may still contain nodes. Since they are already sorted, we can simply append the entire remaining portion by setting tail.next to the head of the non-empty list.
6. The head of the final merged list is dummy.next.

This process is visualized perfectly in the following diagram.

The following video from takeUforward provides an excellent walkthrough of this optimal method.

Finally, review the Java implementation in the takeUforward article to see the complete, production-ready code.

This iterative approach is the one you should aim for in an interview.

• Time Complexity: O(N1 + N2), as we traverse both lists once.
• Space Complexity: O(1), as we only use a few extra pointers and reuse the existing nodes.

Practice Problem

You are now ready to implement this on your own. This is a very common LeetCode problem. Try to code all three solutions: brute-force, recursive, and finally, the optimal iterative one.

• LeetCode 21: Merge Two Sorted Lists

Conclusion

In this lesson, we explored three different ways to merge two sorted linked lists, demonstrating a clear progression from a simple but inefficient solution to a highly optimized one. Understanding these trade-offs is crucial for interview success.

Key Takeaways:

• Brute-Force: Simple to conceptualize (collect, sort, rebuild) but inefficient with O(N log N) time and O(N) space.
• Recursive: An elegant solution that leverages the sorted property for O(N1 + N2) time but incurs O(N1 + N2) space complexity due to the call stack.
• Optimal (Iterative): The interview-standard solution. It uses a two-pointer technique and a dummy head node to merge the lists in O(N1 + N2) time and O(1) space by rewiring existing nodes.

In our next lesson, we will tackle another classic problem: determining if a linked list is a palindrome. This will challenge you to combine several techniques we've learned, including list reversal and the slow-fast pointer pattern, to achieve an optimal O(1) space solution.