Skip to content

Merge Two Sorted Lists

LeetCode Problem #21 | Difficulty: Easy | Topic: Linked List/Recursion

🔗 Problem Link: Merge Two Sorted Lists - LeetCode

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Visual representation:
list1: 1 → 2 → 4
list2: 1 → 3 → 4
result: 1 → 1 → 2 → 3 → 4 → 4

Example 2:

Input: list1 = [], list2 = []
Output: []

Visual representation:
list1: null
list2: null  
result: null

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Visual representation:
list1: null
list2: 0
result: 0

Constraints:

  • The number of nodes in both lists is in the range [0, 50]
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order

🚀 Quick Revision Notes (1-Minute Read)

🎯 Optimal Approach: Iterative with Dummy Head | Time: O(m+n) | Space: O(1)

💡 Key Insight: Use a dummy head to simplify edge cases and maintain a pointer to build the result list.

🔥 Optimization Strategy:

  1. Dummy Head: Start with dummy node to avoid null checks
  2. Two Pointers: Compare values and link smaller node
  3. Append Remaining: Link remaining nodes from non-empty list
  4. Return: Return dummy.next as the actual head

⚡ Quick Implementation: 

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    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;
    }

    // Append remaining nodes
    current.next = (list1 != null) ? list1 : list2;

    return dummy.next;
}

🎪 Step-by-Step Pattern: 

list1: 1 → 2 → 4
list2: 1 → 3 → 4

Step 1: Compare 1 vs 1 → choose list1(1), advance list1
Step 2: Compare 2 vs 1 → choose list2(1), advance list2  
Step 3: Compare 2 vs 3 → choose list1(2), advance list1
Step 4: Compare 4 vs 3 → choose list2(3), advance list2
Step 5: Compare 4 vs 4 → choose list1(4), advance list1
Step 6: list1 empty → append remaining list2(4)

Result: 1 → 1 → 2 → 3 → 4 → 4

🚫 Common Mistakes:

  • Forgetting to handle null input lists
  • Not advancing pointers correctly
  • Missing the remaining nodes after one list is exhausted
  • Complex null checks without dummy head

📝 Pattern Recognition: Classic "merge pattern" fundamental for merge sort and k-way merge algorithms.

Understanding the Problem

Key Points:

  1. Input Constraint: Both lists are already sorted in non-decreasing order
  2. Merge Operation: Combine two lists while maintaining sorted order
  3. Node Reuse: Splice existing nodes, don't create new ones
  4. Edge Cases: Handle empty lists gracefully

What Makes This Fundamental:

  • Linked List Manipulation: Core pointer operations
  • Merge Algorithm: Foundation for merge sort
  • Two Pointers Technique: Essential algorithmic pattern
  • Recursion vs Iteration: Can be solved both ways

Visual Understanding:

Merge Process Visualization:

Initial State:
list1: 1 → 2 → 4 → null
list2: 1 → 3 → 4 → null
result: dummy → null

Step-by-step merge:
Compare 1 vs 1: take list1
result: dummy → 1
list1: 2 → 4 → null

Compare 2 vs 1: take list2  
result: dummy → 1 → 1
list2: 3 → 4 → null

Compare 2 vs 3: take list1
result: dummy → 1 → 1 → 2
list1: 4 → null

Compare 4 vs 3: take list2
result: dummy → 1 → 1 → 2 → 3
list2: 4 → null

Compare 4 vs 4: take list1
result: dummy → 1 → 1 → 2 → 3 → 4
list1: null

Append remaining list2:
result: dummy → 1 → 1 → 2 → 3 → 4 → 4

The Core Challenge:

Problem: Merge two sorted linked lists efficiently

Key considerations:
1. Maintain sorted order
2. Handle null pointers
3. Reuse existing nodes
4. Minimize space usage

Two main approaches:
1. Iterative: Use dummy head and two pointers
2. Recursive: Natural merge logic with recursion

Approaches

Idea: Use a dummy head node to simplify the merging logic.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    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;
    }

    // Append remaining nodes
    current.next = (list1 != null) ? list1 : list2;

    return dummy.next;
}

Detailed Explanation of Iterative Approach

Core Concept: Use a dummy node to avoid complex null checks and maintain a current pointer to build the result.

Step-by-Step Process: 

Example: list1 = [1,2,4], list2 = [1,3,4]

Initial:
dummy → null
current = dummy
list1 → 1 → 2 → 4 → null
list2 → 1 → 3 → 4 → null

Iteration 1: Compare 1 vs 1
- list1.val (1) <= list2.val (1) ✓
- current.next = list1 → dummy → 1
- list1 = list1.next → list1 → 2 → 4 → null
- current = current.next → current = 1

Iteration 2: Compare 2 vs 1  
- list1.val (2) <= list2.val (1) ✗
- current.next = list2 → dummy → 1 → 1
- list2 = list2.next → list2 → 3 → 4 → null
- current = current.next → current = 1 (second one)

Iteration 3: Compare 2 vs 3
- list1.val (2) <= list2.val (3) ✓
- current.next = list1 → dummy → 1 → 1 → 2
- list1 = list1.next → list1 → 4 → null
- current = current.next → current = 2

Iteration 4: Compare 4 vs 3
- list1.val (4) <= list2.val (3) ✗
- current.next = list2 → dummy → 1 → 1 → 2 → 3
- list2 = list2.next → list2 → 4 → null
- current = current.next → current = 3

Iteration 5: Compare 4 vs 4
- list1.val (4) <= list2.val (4) ✓
- current.next = list1 → dummy → 1 → 1 → 2 → 3 → 4
- list1 = list1.next → list1 = null
- current = current.next → current = 4

End loop (list1 is null):
- current.next = list2 → dummy → 1 → 1 → 2 → 3 → 4 → 4
- Return dummy.next → 1 → 1 → 2 → 3 → 4 → 4

Time Complexity: O(m + n) - visit each node exactly once

Space Complexity: O(1) - only constant extra space

Approach 2: Recursion

Idea: Use recursive calls to naturally handle the merge logic.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // Base cases
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    // Recursive case
    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

Detailed Explanation of Recursive Approach

Core Concept: At each step, choose the smaller head and recursively merge the remaining lists.

Recursion Tree for [1,2,4] and [1,3,4]: 

mergeTwoLists([1,2,4], [1,3,4])
├── 1 <= 1 ✓, choose list1[1]
└── mergeTwoLists([2,4], [1,3,4])
    ├── 2 <= 1 ✗, choose list2[1]
    └── mergeTwoLists([2,4], [3,4])
        ├── 2 <= 3 ✓, choose list1[2]
        └── mergeTwoLists([4], [3,4])
            ├── 4 <= 3 ✗, choose list2[3]
            └── mergeTwoLists([4], [4])
                ├── 4 <= 4 ✓, choose list1[4]
                └── mergeTwoLists(null, [4])
                    └── return [4]

Result builds up: 1 → 1 → 2 → 3 → 4 → 4

Time Complexity: O(m + n) - each node processed once

Space Complexity: O(m + n) - recursion call stack

Approach 3: Iterative without Dummy Head

Idea: Handle the first node separately, then proceed with the merge.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;

    ListNode head, current;

    // Initialize head
    if (list1.val <= list2.val) {
        head = current = list1;
        list1 = list1.next;
    } else {
        head = current = list2;
        list2 = list2.next;
    }

    // Merge remaining
    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;
    }

    // Append remaining
    current.next = (list1 != null) ? list1 : list2;

    return head;
}

Detailed Explanation of No Dummy Head Approach

Core Concept: Explicitly handle the head initialization to avoid using a dummy node.

Why More Complex: 

Without dummy head, we need to:
1. Handle null inputs first
2. Determine which list provides the head
3. Initialize both head and current pointers
4. Then proceed with normal merge logic

With dummy head:
1. Create dummy node
2. Start merge loop immediately  
3. Return dummy.next

Dummy head approach is cleaner and less error-prone

Time Complexity: O(m + n) - same merge process

Space Complexity: O(1) - no extra space except pointers

Edge Cases and Testing

Critical Edge Cases:

  1. Both Lists Empty: 

    Input: list1 = null, list2 = null
Output: null

  2. One List Empty: 

    Input: list1 = [1,2,3], list2 = null
Output: [1,2,3]

Input: list1 = null, list2 = [1,2,3]
Output: [1,2,3]

  3. Equal Elements: 

    Input: list1 = [1,1,1], list2 = [1,1,1]  
Output: [1,1,1,1,1,1]

  4. No Overlap: 

    Input: list1 = [1,2,3], list2 = [4,5,6]
Output: [1,2,3,4,5,6]

  5. Different Lengths: 

    Input: list1 = [1], list2 = [1,3,4,5,6]
Output: [1,1,3,4,5,6]

Test Cases for Validation:

// Edge cases
mergeTwoLists(null, null) → null
mergeTwoLists([1,2,3], null) → [1,2,3]
mergeTwoLists(null, [1,2,3]) → [1,2,3]

// Basic cases
mergeTwoLists([1,2,4], [1,3,4]) → [1,1,2,3,4,4]
mergeTwoLists([1], [2]) → [1,2]
mergeTwoLists([2], [1]) → [1,2]

// Equal elements
mergeTwoLists([1,1], [1,1]) → [1,1,1,1]

// Different lengths
mergeTwoLists([1,2], [3,4,5,6,7]) → [1,2,3,4,5,6,7]
mergeTwoLists([5,6,7], [1,2,3,4]) → [1,2,3,4,5,6,7]

// No overlap
mergeTwoLists([1,3,5], [2,4,6]) → [1,2,3,4,5,6]

Key Insights and Patterns

Why This Problem is Fundamental:

  1. Merge Pattern: Foundation for merge sort algorithm
  2. Linked List Manipulation: Essential pointer techniques
  3. Two Pointers: Classic algorithmic pattern
  4. Recursion: Natural recursive structure

Common Applications:

  • Merge Sort: Core subroutine for divide-and-conquer sorting
  • K-way Merge: Extends to merging multiple sorted lists
  • Database Operations: Merging sorted result sets
  • Stream Processing: Combining sorted data streams
  • #23 Merge k Sorted Lists (Hard) - Extension to multiple lists
  • #88 Merge Sorted Array (Easy) - Array version of merge
  • #148 Sort List (Medium) - Merge sort for linked lists
  • #1634 Add Two Polynomials (Medium) - Similar merge logic

Templates and Quick Reference

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    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;
    }

    current.next = (list1 != null) ? list1 : list2;
    return dummy.next;
}

Recursive Template:

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

Memory Aid:

Merge Two Sorted Lists Pattern:
1. DUMMY HEAD: Simplifies edge cases
2. TWO POINTERS: Compare and advance smaller value
3. APPEND REMAINING: Link leftover nodes 
4. RETURN DUMMY.NEXT: Skip dummy node

Visual Memory:
list1: 1 → 2 → 4
list2: 1 → 3 → 4
       ↓   ↓   ↓
Compare → Link → Advance

Remember: "Choose smaller, link, advance, repeat!"