LeetCode 21: Merge Two Sorted Lists

Merge Two Sorted Lists – LeetCode Solution (C++)

Merging two sorted lists is a classic linked list problem that is frequently asked in coding interviews. In this article, we will cover the optimal approach, step-by-step explanations, dry runs, alternative methods, and complexity analysis.

---

Problem Statement

LeetCode 21: Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list.
Return the head of the merged linked list.
The merged list should be sorted in non-decreasing order.

Example 1

Input:

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

Output:

[1,1,2,3,4,4]

Example 2

Input:

list1 = [], list2 = []

Output:

[]

Example 3

Input:

list1 = [], list2 = [0]

Output:

[0]

---

Optimal Approach – Two Pointers (Iterative)

Since both lists are already sorted, we can efficiently merge them using the two-pointer technique.

1. Create a dummy node that helps in building the merged list.
2. Use a pointer curr to track the last node of the merged list.
3. Traverse both lists while comparing the current nodes:
   • Append the smaller node to curr.
   • Move the respective pointer forward.
4. If any list remains, attach it to the merged list.
5. Return dummy->next as the new head.

Time Complexity

• O(N + M) → We traverse both lists only once.

Space Complexity

• O(1) → No extra space is used apart from pointers.

---

C++ Solution (LeetCode Compatible)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy;  // Dummy node to simplify edge cases
        ListNode* curr = &dummy;  // Pointer to track the merged list
        
        while (list1 && list2) {
            if (list1->val < list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        
        // Attach the remaining part
        if (list1) curr->next = list1;
        if (list2) curr->next = list2;
        
        return dummy.next;  // Return merged list
    }
};

---

Step-by-Step Code Explanation

1. Initialize a Dummy Node

   • ListNode dummy; creates a dummy node to simplify list merging.
   • ListNode* curr = &dummy; keeps track of the last node in the merged list.

2. Traverse the Lists

   • While both lists have nodes, compare values:
     • Attach the smaller node to curr->next.
     • Move the corresponding list pointer forward.
     • Move curr forward to keep track of the merged list.

3. Attach Remaining Nodes

   • If either list is not empty after the loop, attach the remaining nodes.

4. Return the Merged List

   • Since we used a dummy node, dummy.next points to the actual head.

---

Dry Run (Step-by-Step Execution)

Example Input

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

Stepwise Merging Process

Step	list1	list2	Merged List
1	1 → 2 → 4	1 → 3 → 4	1
2	2 → 4	1 → 3 → 4	1 → 1
3	2 → 4	3 → 4	1 → 1 → 2
4	4	3 → 4	1 → 1 → 2 → 3
5	4	4	1 → 1 → 2 → 3 → 4
6	NULL	4	1 → 1 → 2 → 3 → 4 → 4

Final Output

[1, 1, 2, 3, 4, 4]

---

Alternative Approaches

1. Brute Force (Concatenate & Sort)

1. Copy all nodes from both lists into an array.
2. Sort the array.
3. Create a new linked list from the sorted array.

Time Complexity: O(N log N) (due to sorting)
Space Complexity: O(N + M) (extra space for array)
❌ Not optimal because sorting is unnecessary.

---

2. Recursive Approach

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;

        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

✅ More elegant but uses extra stack space.

Time Complexity: O(N + M)
Space Complexity: O(N + M) (Recursive calls use stack memory)
❌ Not recommended for large inputs due to stack overflow risk.

---

Best Solution & Comparison

Approach	Time Complexity	Space Complexity	Notes
Two Pointers (Iterative) ✅	O(N + M)	O(1)	✅ Best choice, no extra space
Recursive	O(N + M)	O(N + M)	❌ Uses stack space
Brute Force (Sort & Merge)	O(N log N)	O(N + M)	❌ Unnecessary sorting overhead

Why the Two-Pointer Approach is Best?

✔ Uses O(1) extra space (efficient memory usage).
✔ Processes elements in O(N + M) time (linear traversal).
✔ No recursion depth issues.

---

Conclusion

• Best approach: Two-pointer iterative method
• Why? Optimal time complexity and constant space usage.
• Alternative: Recursive solution (cleaner but uses extra space).
• Practice More:
  • Merge k Sorted Lists (Hard)
  • Sort List (Medium)
  • Remove Duplicates from Sorted List

Would you like more similar tutorials? Let me know!