Merging Sorted Linked Lists

1. The Merging Problem

The task is straightforward: you are given the heads of two linked lists, both sorted in non-decreasing order. Your goal is to merge them into a single, sorted linked list. The new list should be created by "splicing" together the nodes from the original two lists.

For example, given:

• list1: 5 -> 10 -> 15
• list2: 2 -> 3 -> 20

The merged list should be:

• result: 2 -> 3 -> 5 -> 10 -> 15 -> 20

A key constraint, crucial for interviews, is that we should aim to do this in-place, meaning we should rearrange the next pointers of the existing nodes rather than creating a new node for every single element. This is what allows for an $O(1)$ space solution.

2. The Iterative Approach and a Common Hurdle

The basic logic seems simple. We can maintain two pointers, one at the head of each list, say p1 and p2.

1. Compare the values at p1 and p2.
2. The node with the smaller value becomes the next node in our merged list.
3. We then advance the pointer of the list from which we took the node.
4. We repeat this process until one of the lists is fully traversed.

This sounds good, but there's a practical hurdle: how do we manage the head of the new merged list? The first node of our result could come from list1 or list2. Handling this as a special "if" condition at the beginning makes the code clunky. We would need to write separate logic to initialize the head and then a loop to handle the rest.

This is where a powerful and common linked list pattern comes into play: the dummy node.

3. The Elegant Solution: Using a Dummy Node

A dummy node (or sentinel node) is a placeholder that we place at the very beginning of our result list. It doesn't hold any meaningful data itself, but it acts as a fixed starting point. This completely eliminates the need to handle the head of the list as a special case.

Here is the refined algorithm:

1. Create a dummy node. This can be new Node(-1) or any other placeholder value.
2. Create a current pointer and initialize it to point to the dummy node. This current pointer will always track the last node in our merged list, making it easy to append the next one.
3. Iterate as long as both list1 and list2 are not null:
   • If list1.data <= list2.data, we append list1 to our merged list by setting current.next = list1. Then, we advance list1 to its next node.
   • Otherwise, we append list2 by setting current.next = list2. Then, we advance list2.
   • Crucially, after appending, we must also advance our current pointer to the node we just added (current = current.next).
4. Once the loop finishes, one of the lists is exhausted. The other list might still contain nodes. Since that list is already sorted, we can simply append its entire remaining part to the end of our merged list.
5. Finally, the head of the truly merged list is dummy.next. We return this.

The following image provides a great step-by-step visualization of this process.

To see this logic explained and implemented in code, the following video is an excellent resource.

4. Java Implementation and Analysis

The dummy node approach leads to very clean and concise code. Let's look at a textual reference that provides a clear implementation.

The core of the logic, which you'll find in the resources, looks like this:

// Assume a ListNode class is defined
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. Create a dummy node to act as the starting point.
        ListNode dummy = new ListNode(-1);
        
        // 2. Create a 'current' pointer to build the new list.
        ListNode current = dummy;

        // 3. Loop while both lists have nodes.
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1; // Append node from list1
                list1 = list1.next;   // Move list1's pointer
            } else {
                current.next = list2; // Append node from list2
                list2 = list2.next;   // Move list2's pointer
            }
            current = current.next;   // Move the current pointer forward
        }

        // 4. At least one list is now null. Append the remaining non-null list.
        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        // 5. The merged list starts after the dummy node.
        return dummy.next;
    }
}

Complexity Analysis

• Time Complexity: $O(N+M)$, where $N$ and $M$ are the number of nodes in list1 and list2, respectively. We must traverse every node in both lists once to construct the merged list.
• Space Complexity: $O(1)$. This is a major advantage. We only use a few extra pointers (dummy, current). We are not allocating new memory for the list's nodes; we are simply rearranging the pointers of the existing ones. This is exactly what interviewers look for in an optimal solution.

Conclusion

Great job! You've now mastered another essential linked list algorithm. This problem is a perfect example of how a simple pattern can significantly simplify your code and help you avoid tricky edge cases.

Key Takeaways:

• Merging two sorted lists can be done efficiently with an iterative, two-pointer approach.
• The dummy node is a fundamental technique for linked list problems involving list construction. It provides a stable anchor point, simplifying the logic for handling the list's head.
• The optimal iterative solution achieves $O(N+M)$ time complexity and, importantly, $O(1)$ auxiliary space complexity.

Preview of the next lesson:
In this lesson, we saw how a dummy node tidied up our merging logic. This pattern is so useful that it deserves its own focus. In the next lesson, we will explore how to apply the dummy node technique as a general-purpose tool to simplify other linked list manipulation problems, such as removing nodes that meet specific criteria.