Merge Two Sorted Lists Algorithm Solution

The merge two sorted lists problem requires combining two ordered linked lists into a single sorted list. This classic algorithmic challenge tests understanding of linked list manipulation, pointer arithmetic, and algorithmic efficiency in technical interviews at top tech companies.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we mutate the input lists, or must we create new nodes?
2. What is the expected time complexity constraint? O(n + m) is optimal, but are there additional requirements?
3. Are the input lists guaranteed to be sorted in ascending order?
4. What is the maximum size of each list? This affects whether we should consider memory constraints.
5. Should we return a new merged list or modify one of the existing lists?

Restatement in my own words: Given two sorted linked lists, merge them into a single sorted linked list by splicing together the nodes from both lists. The merged list should maintain the ascending order of elements.

Problem constraints and assumptions:

• Input lists are guaranteed to be sorted in non-decreasing order
• Lists can be empty (0 or more elements)
• Each list node contains an integer value and a pointer to the next node
• We can assume valid linked list structures (no cycles)
• The merged result must also be a properly ordered sorted list

Data shape and structure:

• Input: Two singly linked lists where each node has val (int) and next (ListNode)
• Output: A new singly linked list with all elements from both inputs in sorted order
• The lists can have different lengths (e.g., one list has 3 nodes, another has 5)

This is a classic merge operation that appears in merge sort and other divide-and-conquer algorithms. The key insight is to use a two-pointer technique to efficiently traverse both lists and build the result in linear time.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern is "Two Pointers" or "Merge Process", combined with "Linked List Traversal".

Why this problem fits that pattern

The problem explicitly asks to merge two sorted lists, which is a classic merge operation found in merge sort. The key signals are:

• Two sorted inputs that need to be combined
• Sequential comparison of elements from both lists
• Maintaining the sorted order in the output

Core insight needed to solve it

The core insight is that since both input lists are already sorted, we can efficiently merge them by always selecting the smaller of the two current elements from each list. This creates a natural "merge" operation that's O(n + m) time complexity.

The pattern is not just about merging, but about "Merging Sorted Sequences" - a fundamental algorithmic pattern that appears in merge sort, external sorting, and many other problems where we need to combine multiple sorted datasets efficiently.

This pattern is characterized by:

1. Two ordered sequences that need to be combined
2. A simple comparison operation between current elements
3. Sequential processing with minimal state tracking
4. Linear time complexity due to the ordered nature of inputs

This insight allows us to avoid more complex approaches like sorting or additional data structure usage, and instead leverage the inherent ordering to achieve optimal performance.

3. Approach Evolution

My first instinct is to use a two-pointer technique because this problem involves merging two sorted sequences, which naturally suggests comparing elements from both lists and advancing the pointer of whichever element is smaller. But that's O(n+m) time because we need to examine each element at least once, and O(1) extra space if we do it in-place. Let me think about how to optimize this approach.

The brute force approach would be to collect all elements from both lists into one array, sort it, and return. But that's O((n+m) log(n+m)) time because we're sorting all elements together, and it's not optimal since we already have the lists sorted. Also, we're using extra space for the array.

I notice that if I maintain the invariant that both lists are already sorted, I can reduce it to O(n+m) time by simply comparing the current elements from each list and appending the smaller one to our result. This is optimal because we must look at every element at least once to merge them.

The key insight is that since both lists are sorted, I can always safely pick the smaller of the two current elements without worrying about missing any elements that should come later. I just need to handle the case where one list gets exhausted before the other.

My approach will be:

1. Use a dummy head node to simplify list construction
2. Compare current elements from both lists and advance the pointer of the smaller one
3. Handle remaining elements from whichever list still has items left
4. Return the merged list starting from dummy.next

This maintains the sorted property throughout the process and ensures all elements are included exactly once.

Important invariants that must hold:

• At each step, the current element from list1 is ≤ all remaining elements in list1
• At each step, the current element from list2 is ≤ all remaining elements in list2
• The merged result maintains sorted order throughout construction
• We never skip elements or process the same element twice

4. Data Structure Choice

For this problem, I'll use a dummy head node approach with pointers to traverse and merge the two sorted lists.

Primary Data Structures Used

1. Dummy Head Node (ListNode) - This is the primary structure that simplifies edge case handling and maintains a clean reference to the merged list's start. It eliminates special handling for the first node insertion.

2. Pointers (ListNode) - I'll use three pointers:

   • current: Points to the current node in the merged list being built
   • list1 and list2: Point to the current nodes in each input list being compared

Why Each Data Structure Is Needed

The dummy head node is essential because:

• It eliminates the need to handle the first node insertion specially
• It provides a consistent reference point for building the merged list
• It reduces edge case complexity (empty lists, single element lists)
• It makes the pointer manipulation cleaner and less error-prone

The pointers are necessary because:

• They allow for O(1) comparisons between list nodes
• They enable in-place merging without requiring additional space for new nodes
• They maintain the sorted order by always selecting the smaller current element

Time and Space Impact

Time Complexity: O(1) for each node operation, but O(m+n) overall where m and n are list lengths Space Complexity:

• O(1) additional space for the dummy node (constant extra space)
• O(1) for the three pointers (constant space)
• Overall: O(1) extra space, which is optimal for this in-place merge operation

Helper Structure

The dummy head node serves as a helper structure that simplifies the implementation by:

• Providing a stable anchor point for list construction
• Eliminating special-case logic for the first node
• Making the code more readable and maintainable

This approach is optimal because it uses minimal additional space while maintaining clean, readable logic that handles all edge cases naturally.

5. Algorithm Walkthrough

Let me trace through the algorithm with the example where list1 = [1,2,4] and list2 = [1,3,4].

Step 1: Initialize pointers at the heads of both lists:

• current1 = 1 (from list1)
• current2 = 1 (from list2)
• mergedHead = null

Step 2: Compare values and select the smaller one:

• Both current values are 1, so we pick list1's 1
• Create new node with value 1
• mergedHead = new ListNode(1)
• Advance current1 to point to 2

Step 3: Continue comparison:

• current1 = 2, current2 = 1
• 1 < 2, so pick list2's 1
• mergedHead.next = new ListNode(1)
• Advance current2 to point to 3

Step 4: Continue comparison:

• current1 = 2, current2 = 3
• 2 < 3, so pick list1's 2
• mergedHead.next = new ListNode(2)
• Advance current1 to point to 4

Step 5: Continue comparison:

• current1 = 4, current2 = 3
• 3 < 4, so pick list2's 3
• mergedHead.next = new ListNode(3)
• Advance current2 to point to 4

Step 6: Continue comparison:

• current1 = 4, current2 = 4
• Values are equal, pick list1's 4
• mergedHead.next = new ListNode(4)
• Advance current1 to point to null

Step 7: Handle remaining elements:

• current1 = null, current2 = 4
• Since current1 is null, append remaining list2 elements
• mergedHead.next = new ListNode(4)
• Advance current2 to point to null

Step 8: Final termination:

• Both pointers are null, algorithm terminates
• Result: [1,1,2,3,4]

The key invariant maintained throughout is that we always select the smaller current element and advance that list's pointer, ensuring we never skip any elements or create duplicates. The algorithm correctly handles the case where one list is exhausted before the other by appending the remaining elements.

graph LR
    A[1] --> B[1] --> C[2] --> D[3] --> E[4]
    F[1] --> G[3] --> H[4]
    I[merged] --> J[1] --> K[1] --> L[2] --> M[3] --> N[4]

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 Solution {
    /**
     * Merges two sorted linked lists into one sorted linked 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 node 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;
    }
}

The solution uses a dummy head node to simplify the merging logic and avoid special handling for the first node. We maintain a pointer to the current position in the merged list and advance the appropriate input list pointer based on value comparison. After one list is exhausted, we append any remaining nodes from the other list.

7. Complexity Analysis

Time Complexity: O(m + n) where m and n are the lengths of the two input lists.

The algorithm performs a single pass through both lists, visiting each node exactly once. At each step, we perform constant time operations (comparisons and pointer updates). Since we process at most m + n nodes total, the time complexity is linear in the combined size of the inputs.

Space Complexity: O(1)

The solution uses only a constant amount of extra space for the dummy node and pointer variables. No additional data structures are created that scale with input size. The new merged list is constructed by reusing existing nodes from the input lists, so no additional memory allocation is required beyond a few reference variables.

Why these bounds are correct:

The linear time complexity is optimal for this problem because we must examine each element at least once to determine its position in the merged result. Since we're merging two sorted lists, there's no way to avoid processing all elements.

The constant space complexity follows from the fact that we're not creating any new data structures that grow with input size. We only maintain a few pointers and one dummy node, which are independent of the input list sizes.

Is this optimal?

Yes, this solution achieves optimal time and space complexity for the merge operation. Any correct solution must process each element at least once (O(m + n) time lower bound), and the space usage cannot be reduced below O(1) since we're not allowed to create new nodes or use additional data structures that scale with input size.

8. Edge Cases & Pitfalls

Empty and minimal inputs

• When one or both lists are empty, the solution must handle these gracefully. If list1 is null and list2 has elements, we should return list2. Similarly for the reverse case.
• When one list is empty and the other has one element, we should return that single-element list as-is.

Duplicate values and repeated states

• The algorithm must properly handle duplicate values in either list. For example, if both lists contain the same value at different positions, our merge should preserve all occurrences.
• If both lists have identical elements in the same order, we must ensure they're merged correctly without skipping or duplicating any nodes.

Boundary conditions

• Lists of size 0, 1, and n where n is large.
• When one list is significantly longer than the other (e.g., one has 1000 elements and another has 1).
• The case where we're merging the same list with itself (though this is a degenerate case in most practical applications).

Common implementation mistakes

• Incorrect pointer management: Failing to properly update the current pointer and losing track of the merged list head.
• Missing null checks: Not checking if list1 or list2 is null before accessing their next fields, which leads to NullPointerException.
• Incorrect list traversal: Advancing the wrong pointer or not advancing at all, leading to infinite loops or incomplete merges.
• Not handling the final node correctly: Forgetting to set current.next = null or not properly connecting the last node in the merged list.
• Modifying input lists: If the problem requires not mutating the input lists, we must create new nodes rather than reusing existing ones.

Implementation-specific issues

• Using list1 != null && list2 != null condition in the while loop without considering that one list might be exhausted, leading to incomplete merging.
• Not initializing head and current properly, which can cause the first node to be lost or duplicated.
• Confusing list1.val and list2.val comparisons with actual node references, potentially causing incorrect ordering.

9. Alternative Approaches

There are several alternative approaches to solving the merge two sorted lists problem, each with different trade-offs:

1. Recursive Approach:

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;
    }
}

This approach is elegant and mirrors the problem's definition directly. However, it uses O(m+n) space on the call stack in worst case, making it less suitable for very large lists where stack overflow might occur.

2. Using Extra Space (Array/List): Create a new list by collecting all elements from both lists, sorting them, and then building the result. This approach has O((m+n) log(m+n)) time complexity due to sorting, which is worse than our optimal O(m+n) solution. It's only useful when we need to handle multiple sorted lists or want to leverage existing sorting algorithms.

3. In-Place Reordering with Dummy Node: Instead of using a dummy node, we can use a more complex pointer manipulation approach that avoids the dummy node entirely but requires careful handling of edge cases and null checks.

The iterative approach with dummy node is preferred because it provides clean, readable code with optimal time complexity O(m+n) and space complexity O(1), making it the most practical solution for production systems where memory efficiency matters.

The recursive approach is more intuitive but less efficient in terms of space usage, while the sorting-based approach is inefficient due to unnecessary sorting operations. Our chosen solution strikes the best balance between readability, performance, and memory usage for real-world applications.

10. Test Cases

public class MergeTwoSortedLists {
    
    public static void main(String[] args) {
        // Test Case 1: Basic case with different lengths
        ListNode l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode l2 = new ListNode(2, new ListNode(4, new ListNode(6, new ListNode(8))));
        ListNode result = mergeTwoLists(l1, l2);
        // Expected: [1,2,3,4,5,6,8]
        
        // Test Case 2: One list is empty
        ListNode l3 = null;
        ListNode l4 = new ListNode(1, new ListNode(2, new ListNode(3)));
        ListNode result2 = mergeTwoLists(l3, l4);
        // Expected: [1,2,3]
        
        // Test Case 3: Both lists empty
        ListNode result3 = mergeTwoLists(null, null);
        // Expected: null
        
        // Test Case 4: Single element lists
        ListNode l5 = new ListNode(1);
        ListNode l6 = new ListNode(2);
        ListNode result4 = mergeTwoLists(l5, l6);
        // Expected: [1,2]
        
        // Test Case 5: Lists with duplicates
        ListNode l7 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode l8 = new ListNode(1, new ListNode(3, new ListNode(5)));
        ListNode result5 = mergeTwoLists(l7, l8);
        // Expected: [1,1,3,3,5,5]
        
        // Test Case 6: One list is longer with duplicates
        ListNode l9 = new ListNode(1, new ListNode(1, new ListNode(2)));
        ListNode l10 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode result6 = mergeTwoLists(l9, l10);
        // Expected: [1,1,1,2,3,4]
    }
    
    public static 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;
    }
    
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}

11. Final Summary

11. Final Summary

The core idea is to merge two sorted linked lists by comparing nodes one at a time and building the result list in-place. This solution works efficiently by leveraging the sorted property to avoid full sorting, achieving optimal O(m+n) time complexity where m and n are the lengths of the input lists. The key insight is using a dummy head node to simplify edge case handling and maintain clean pointer manipulation throughout the merge process.

11. Final Summary

The core idea is to efficiently merge two sorted linked lists by iteratively selecting the smaller head node and building the result list in linear time. This solution works because it leverages the 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 for this problem since we must examine each element at least once to construct the merged result, making the linear time complexity unavoidable. The clean iterative implementation with a dummy head node elegantly handles all edge cases including empty lists and different sized inputs.