L23: Merge Two Sorted Linked Lists

Merging two sorted linked lists is a foundational algorithmic problem in Data Structures and Algorithms (DSA). This chapter explores how to combine two sorted linked lists into a single sorted linked list, evolving from a naive brute-force approach requiring extra memory and sorting algorithms to an optimal, in-place pointer-manipulation technique with $O(1)$ space complexity.

1. Problem Statement & Objective

We are given two sorted linked lists, L1 and L2. Our objective is to combine all elements from both lists, maintain their sorted order, and return the head of the newly merged linked list L3.

2. Naive Brute-Force Approach: Arrays and Sorting

The Strategy

A straightforward way to solve this problem without worrying about complex pointer rearrangements is to treat the linked lists simply as collections of data:

1. Traverse L1 and collect all its element values into an auxiliary container (an array).
2. Traverse L2 and collect all its element values into the same array.
3. Sort the combined array using a standard sorting algorithm.
4. Convert the sorted array back into a brand new linked list (L3).
5. Return the head of L3.

Pseudocode for Naive Approach

public Node mergeTwoLists(Node head1, Node head2) {
    ArrayList<Integer> arr = new ArrayList<>();
    
    // Traverse L1 and collect elements
    Node t1 = head1;
    while (t1 != null) {
        arr.add(t1.data);
        t1 = t1.next;
    }
    
    // Traverse L2 and collect elements
    Node t2 = head2;
    while (t2 != null) {
        arr.add(t2.data);
        t2 = t2.next;
    }
    
    // Sort the combined array
    Collections.sort(arr);
    
    // Convert sorted array back to a Linked List
    return convertArrayToLinkedList(arr);
}

Complexity Analysis of Naive Approach

• Time Complexity: $O(N_1 + N_2 + N \log N + N)$, where $N_1$ is the size of L1, $N_2$ is the size of L2, and $N = N_1 + N_2$ is the total number of elements. The sorting step dominates with $O(N \log N)$.
• Space Complexity: $O(N)$ auxiliary space for the array plus $O(N)$ space required to allocate brand new nodes for the output list L3.

3. The Optimization Insight: Leveraging Sorted Properties & Two Pointers

Why the Naive Approach Falls Short

An interviewer will typically reject the brute-force method because:

1. It ignores the fact that both input lists are already sorted. Sorting an array from scratch throws away pre-existing order.
2. It wastes memory by instantiating $N$ brand new node objects when the original nodes in L1 and L2 already exist in memory. We can reuse existing nodes by simply rewiring their pointers (next references).

Core Mental Model / Analogy

Real-Life Analogy: Imagine you have two sorted stacks of playing cards. Instead of dumping all cards into a box, shaking them up, sorting them, and printing brand new cards, you simply look at the top card of each stack, pick the smaller one, place it in your final line, and repeat. You never create new cards; you just rearrange where they point.

4. The Dummy Node Technique

When building or rearranging linked lists, handling edge cases—such as initializing the head of the new list or managing empty inputs—can introduce messy conditional checks.

To eliminate this friction, we use a Dummy Node:

• Create a temporary dummy node (e.g., initialized with a placeholder value like -1).
• Maintain a traversal pointer (temporary) anchored at this dummy node.
• As we pick nodes from L1 or L2, we attach them directly to temporary.next.
• At the end of traversal, the actual head of our merged list will simply be dummy.next.

5. Step-by-Step Flow Walkthrough

Let's trace how pointers T1 (on L1), T2 (on L2), and temporary interact during the optimal merge.

Step-by-Step Execution:

1. Compare T1.data (2) and T2.data (1). 1 is smaller.
   • Point temporary.next to T2.
   • Advance temporary to T2.
   • Advance T2 to its next element (3).
2. Compare T1.data (2) and T2.data (3). 2 is smaller.
   • Point temporary.next to T1.
   • Advance temporary to T1.
   • Advance T1 to its next element (4).
3. This comparison loop continues, picking the smaller element from either T1 or T2 and adjusting links in-place without allocating new nodes.

6. Handling Leftover Elements

Once either T1 or T2 reaches null, the comparison loop terminates because one list is fully exhausted. However, nodes remain in the other list.

Because the remaining list is already sorted, we do not need to traverse it node-by-node. We can attach the entire remaining chain in a single pointer assignment:

If T1 is exhausted (T1 == null):
    temporary.next = T2

If T2 is exhausted (T2 == null):
    temporary.next = T1

7. Optimal Implementation (Pseudocode & Structure)

Below is the clean, production-grade logic implementing the two-pointer, in-place node reuse strategy:

public Node mergeTwoLists(Node head1, Node head2) {
    Node t1 = head1;
    Node t2 = head2;
    
    // Create a dummy node to act as the anchor for our merged list
    Node dummyNode = new Node(-1);
    Node temporary = dummyNode;
    
    // Traverse while both lists have active nodes
    while (t1 != null && t2 != null) {
        if (t1.data <= t2.data) {
            temporary.next = t1;
            temporary = t1;
            t1 = t1.next;
        } else {
            temporary.next = t2;
            temporary = t2;
            t2 = t2.next;
        }
    }
    
    // Attach any remaining nodes from either list
    if (t1 != null) {
        temporary.next = t1;
    } else {
        temporary.next = t2;
    }
    
    // Return the head of the merged list, skipping the dummy node
    return dummyNode.next;
}

8. Summary Comparison Table

9. Summary and Key Takeaways

• Problem Definition: Merging two sorted linked lists requires combining all elements from L1 and L2 into a single ordered sequence L3.
• Brute-Force Trap: Collecting elements into an array and sorting them takes $O(N \log N)$ time and $O(N)$ space, failing to leverage the pre-sorted nature of the lists.
• In-Place Optimization: By utilizing the two-pointer technique, we can evaluate elements at the heads of both lists simultaneously in $O(N_1 + N_2)$ time.
• Node Reuse: Instead of instantiating new node objects, we redirect existing next pointers, reducing auxiliary space complexity to $O(1)$.
• Dummy Node Utility: Utilizing a dummy node (-1) simplifies list initialization and removes complex edge-case checks for the head pointer.
• Handling Leftovers: Once one list is exhausted, attach the remainder of the other list in a single pointer assignment rather than traversing it node-by-node.