Merge Two Sorted Lists Algorithm Solution

The merge two sorted lists problem is a fundamental linked list operation that appears frequently in FAANG interviews. This solution presents an iterative approach with O(m+n) time complexity and O(1) space complexity, along with alternative implementations and performance considerations.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are the input lists guaranteed to be sorted, or do we need to handle unsorted inputs?
2. What is the expected size range of the lists? (e.g., small, large, or unbounded)
3. Can we modify the input lists in-place, or must we create a new merged list?
4. Should we return the merged list as a new list or modify one of the existing lists?
5. What is the target time complexity for follow-up optimization? O(n) or better?

Restate the pattern or problem type in your own words: The merge two sorted lists pattern involves combining two pre-sorted arrays or linked lists into a single sorted array or list while maintaining the relative order of elements from both inputs.

Clarify the signal words and constraint shape that point to it:

• "Two sorted arrays/lists" or "given two sorted inputs"
• "Merge" operation in the problem statement
• Expected output should maintain sorted order
• Input constraints often specify that elements are already in ascending order

Note any assumptions you are making:

• Both input lists are sorted in ascending order
• The problem is asking for a merge operation that preserves the sorted property
• We can use standard array/list operations without custom data structures

Identify whether the pattern is best suited for static, streaming, or online scenarios if relevant: This pattern is primarily designed for static input scenarios where both lists are available entirely before processing. It's not well-suited for streaming data where inputs arrive continuously, as the merge operation requires knowledge of both complete lists to maintain sorted order. For streaming scenarios, a different approach like merge sort or priority queue-based merging would be more appropriate.

The core insight is that since both lists are already sorted, we can efficiently merge them by comparing elements from each list one at a time and selecting the smaller element, avoiding the need to re-sort the combined elements.

2. When to Use This Pattern

Signal words and constraint shapes:

• "Two sorted arrays/lists"
• "Merge into one sorted array"
• "Given two sorted inputs"
• "Maintain sorted order in output"
• "Arrays are already ordered"

Why this pattern fits better than alternatives: This pattern is specifically optimized for merging pre-sorted data, making it far more efficient than concatenating and then sorting. While a general sort approach would be O((m+n)log(m+n)), the merge pattern achieves O(m+n) time complexity by leveraging the existing ordering structure.

Conditions where variations apply:

• K-way merge: When more than two sorted lists need merging (use a min-heap approach)
• Streamed data: When lists arrive incrementally rather than all at once (use streaming merge techniques)
• Unsorted data: When lists aren't already sorted, requiring preprocessing with sorting first

Core insight: The key insight is that we can always safely advance the pointer of the smaller element because all remaining elements in that list are guaranteed to be larger than or equal to the current element, maintaining the sorted property of the merged result.

The pattern is ideal for static scenarios where all input data is available upfront, making it perfect for batch processing or when working with pre-sorted datasets that need to be combined efficiently.

3. Approach Evolution

Interview communication script:

"My first instinct is to use a two-pointer technique because I'm dealing with two sorted arrays and need to merge them into one sorted array. But let me think about this more carefully - if I simply iterate through both arrays with two pointers, I can compare elements and pick the smaller one at each step. That's O(n+m) time complexity, which seems optimal for this problem.

But wait, I should consider if there's a more elegant approach. Actually, the two-pointer method is quite clean and intuitive here - I can maintain one pointer for each array and advance the appropriate pointer based on element comparison. This approach is optimal because I need to examine each element at least once to construct the merged sorted result.

Let me think about how I can optimize this further. The key insight is that I don't need to create a new array - I can merge into one of the existing arrays if that's allowed. But since the problem asks to merge two sorted lists, I think the most straightforward approach is to create a new merged list.

The invariant I need to maintain is that at any point, the elements I've already added to my result are in sorted order, and I'm always picking the next smallest element from the remaining unprocessed elements of both lists. This ensures that I never miss a smaller element and that the final result is properly sorted.

I notice that if I maintain this invariant, I can reduce it to O(n+m) time and O(1) extra space (if merging into one of the existing lists), or O(n+m) space if creating a new list. The approach is clean and optimal."

Brute-force approach: The brute force approach would be to append all elements from both lists into one array and then sort the combined array. This is O((n+m) log(n+m)) time complexity, which is clearly suboptimal since we already have sorted lists.

Improved approach: The improved approach uses the two-pointer technique to merge the lists in linear time. We maintain pointers for both input lists and always pick the smaller element at each step, advancing that pointer. This approach is optimal because we must examine each element at least once to construct the merged sorted result.

Final approach with step-by-step reasoning:

1. Initialize two pointers, one for each list, starting at index 0
2. Compare elements at current positions of both lists
3. Add the smaller element to result and advance that list's pointer
4. Continue until one list is exhausted
5. Append remaining elements from the non-empty list to result

Important invariants that must hold:

• At any point, all elements added to the result are in sorted order
• The element at each pointer is the smallest unprocessed element from its respective list
• When one list is exhausted, all remaining elements from the other list can be directly appended

4. Data Structure Choice

For merging two sorted lists, the primary data structure is a linked list or array, depending on the input format and constraints.

Primary Data Structures Used

1. Linked List Nodes - When working with actual ListNode objects, we use the standard ListNode structure with val and next fields
2. Array - When the input is given as arrays, we can work with them directly or use an auxiliary array for the result

Why Each Data Structure Is Needed

Linked List Approach:

• Allows for true O(1) space complexity when returning a new merged list
• Natural fit for the problem since we're combining two ordered sequences
• Maintains the sorted property through pointer manipulation

Array Approach:

• Simpler to implement and debug
• More intuitive for candidates familiar with array operations
• Can be used when the problem allows modification of input arrays

Time and Space Impact

Linked List Solution:

• Time: O(m + n) where m and n are list lengths
• Space: O(1) additional space (not counting the output list)
• No extra allocation beyond the result structure

Array Solution:

• Time: O(m + n) for copying and merging
• Space: O(m + n) for the result array
• Requires additional memory allocation

Helper Structure

The key helper structure is a dummy head node in the linked list approach, which simplifies edge case handling and eliminates special logic for the first node insertion.

The dummy head pattern is essential because:

• It eliminates the need to handle the first node insertion specially
• Reduces null pointer checks in the main loop
• Makes the code cleaner and more readable
• Maintains consistent logic throughout the entire merge process

This choice directly impacts the elegance and correctness of the final implementation, making the dummy head approach the preferred pattern for linked list merging problems.

5. Algorithm Walkthrough

Let me trace through the merge process using the example list1 = [1,3,4] and list2 = [1,2,4].

Step 1: Initialize pointers at the start of both lists: p1 = 0, p2 = 0. Create empty result list.

Step 2: Compare values at current positions: list1[0] = 1 vs list2[0] = 1. Since they're equal, we can take either one - let's take from list1. Add 1 to result. Move p1 forward to 1.

Step 3: Now compare list1[1] = 3 vs list2[0] = 1. Since 1 < 3, take from list2. Add 1 to result. Move p2 forward to 1.

Step 4: Compare list1[1] = 3 vs list2[1] = 2. Since 2 < 3, take from list2. Add 2 to result. Move p2 forward to 2.

Step 5: Compare list1[1] = 3 vs list2[2] = 4. Since 3 < 4, take from list1. Add 3 to result. Move p1 forward to 2.

Step 6: Compare list1[2] = 4 vs list2[2] = 4. Since they're equal, take from list1. Add 4 to result. Move p1 forward to 3.

Step 7: Now p1 = 3, which is beyond list1's length. Add remaining elements from list2: list2[3] = 4 (but index 3 is out of bounds, so we look at list2[2] = 4). Add 4 to result.

Step 8: Both pointers are at end positions. Result list is [1,1,2,3,4,4].

The algorithm terminates correctly because we always process one element at a time from the list with the smaller current value, and once one list is exhausted, we append all remaining elements from the other list.

Edge cases handled:

• One or both lists being empty
• Lists of different lengths
• All elements being equal
• Single element lists

6. Java Solution

/**
 * Definition for singly-linked list node
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class MergeTwoSortedLists {
    
    /**
     * Merges two sorted linked lists into one sorted list
     * @param list1 Head of first sorted linked list
     * @param list2 Head of second sorted linked list
     * @return Head of merged sorted linked list
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Create a dummy head to simplify edge case handling
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // Traverse both lists and merge them in sorted order
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        
        // Attach remaining nodes from either list (if any)
        current.next = (list1 != null) ? list1 : list2;
        
        // Return the merged list starting after dummy node
        return dummy.next;
    }
}

This solution uses a sentinel/dummy node approach to simplify the merging logic and avoid special handling of the first node. The algorithm maintains a pointer to build the result list by comparing values from both input lists and advancing the appropriate pointer. After one list is exhausted, the remaining nodes from the other list are appended directly.

7. Complexity Analysis

Time Complexity: O(m + n) where m and n are the lengths of the two input lists. Each node is visited exactly once during the merge process, and all operations (comparisons, pointer updates) are O(1).

Space Complexity: O(1) for the iterative solution, as we only use a constant amount of extra space for pointers and temporary variables. No additional data structures are created that scale with input size.

The bounds are tight because:

• We must examine each element at least once to determine its final position in the merged list
• The space usage is constant regardless of input size, as we're reusing existing nodes rather than creating new ones

This solution is optimal for the problem constraints. Since we need to produce a merged list containing all elements from both inputs in sorted order, we cannot do better than O(m + n) time complexity. The O(1) space usage is also optimal for an in-place merge operation, as we're not allowed to create additional lists or data structures that grow with input size.

The solution achieves the theoretical lower bounds for this problem type, making it both time and space optimal.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• One or both lists are empty - the algorithm must handle null or zero-length lists gracefully
• Single element lists require careful handling of the termination condition
• Lists of different lengths need to properly append remaining elements

Duplicate values and repeated states

• Duplicate values in either list should be preserved in the merged result
• When both lists have identical elements, the merge must maintain proper ordering
• The algorithm should not inadvertently skip or duplicate elements during traversal

Boundary conditions

• Index out of bounds when accessing list elements (particularly with get() method)
• Empty list access when calling list.get(0) on an empty list
• Iterator or pointer bounds when traversing lists of different sizes

Common implementation mistakes

• Incorrect termination condition: Using list1.size() > 0 && list2.size() > 0 instead of list1 != null && list2 != null can cause NullPointerExceptions
• Missing remaining elements: Failing to append all remaining elements from the non-empty list after one list is exhausted
• Off-by-one errors: Mismanaging loop conditions or index tracking when merging lists of different sizes
• Premature list modification: Modifying input lists in-place when the problem requires preserving original structures
• Incorrect element comparison: Comparing elements with wrong operators or not handling null values properly

The most critical pitfall is assuming that both lists are non-empty after checking one list's size, which can lead to runtime exceptions when one list is empty but the other isn't.

9. Alternative Approaches

There are several alternative approaches to merging two sorted lists, each with different trade-offs:

1. Two-Pointer Approach (Iterative) Instead of using a priority queue, we can use two pointers to traverse both lists simultaneously. This is the most direct approach where we maintain pointers for each list and compare elements at each step.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;
    
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            current.next = list1;
            list1 = list1.next;
        } else {
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    
    // Attach remaining nodes
    current.next = (list1 != null) ? list1 : list2;
    
    return dummy.next;
}

2. Recursive Approach We can solve this recursively by choosing the smaller head node and recursively merging the rest.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

3. Array-Based Merge Convert both lists to arrays, merge them, then reconstruct the list. This is inefficient for large inputs but useful when we need to process elements multiple times.

Comparison of Approaches:

The priority queue approach is more complex than the two-pointer method but useful when we're merging K sorted lists (K-way merge). The recursive approach is elegant but has O(m+n) space complexity due to call stack. The two-pointer iterative approach is optimal for this specific problem with O(1) space and O(m+n) time complexity.

The chosen solution using priority queue is most beneficial when extending to K-way merging scenarios, while the two-pointer approach is more efficient for the simple two-list case.

10. Test Cases

public class MergeTwoSortedListsTest {
    
    @Test
    public void testNormalCase() {
        // Input: list1 = [1,2,4], list2 = [1,3,4]
        // Expected: [1,1,2,3,4,4]
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode expected = new ListNode(1, new ListNode(1, new ListNode(2, 
            new ListNode(3, new ListNode(4, new ListNode(4))))));
        
        assertEquals(expected, mergeTwoLists(l1, l2));
    }
    
    @Test
    public void testEmptyLists() {
        // Input: list1 = [], list2 = []
        // Expected: []
        assertNull(mergeTwoLists(null, null));
        
        // Input: list1 = [], list2 = [0]
        // Expected: [0]
        ListNode l2 = new ListNode(0);
        assertEquals(l2, mergeTwoLists(null, l2));
    }
    
    @Test
    public void testSingleElement() {
        // Input: list1 = [1], list2 = [2]
        // Expected: [1,2]
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode expected = new ListNode(1, new ListNode(2));
        
        assertEquals(expected, mergeTwoLists(l1, l2));
    }
    
    @Test
    public void testDifferentLengths() {
        // Input: list1 = [1,2,3], list2 = [4,5]
        // Expected: [1,2,3,4,5]
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode l2 = new ListNode(4, new ListNode(5));
        ListNode expected = new ListNode(1, new ListNode(2, new ListNode(3, 
            new ListNode(4, new ListNode(5)))));
        
        assertEquals(expected, mergeTwoLists(l1, l2));
    }
    
    @Test
    public void testDuplicateValues() {
        // Input: list1 = [1,1,2], list2 = [1,3,3]
        // Expected: [1,1,1,2,3,3]
        ListNode l1 = new ListNode(1, new ListNode(1, new ListNode(2)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(3)));
        ListNode expected = new ListNode(1, new ListNode(1, new ListNode(1, 
            new ListNode(2, new ListNode(3, new ListNode(3)))));
        
        assertEquals(expected, mergeTwoLists(l1, l2));
    }
}

11. Final Summary

The core idea is to efficiently merge two sorted linked lists into one sorted list by iteratively selecting the smaller head node at each step. This solution works because it leverages the pre-sorted property of both input lists to avoid re-sorting, maintaining O(m+n) time complexity where m and n are the lengths of the input lists. The approach is optimal as it processes each element exactly once and uses constant extra space, making it both time and space efficient for the merge operation.