Leetcode - 21. Merge Two Sorted Lists

# Merging Two Sorted Linked Lists: Approach, Complexity, and Code

Merging two sorted linked lists is a common problem in coding interviews and data structure applications. In this blog, we will discuss different approaches, analyze their time and space complexity, and provide an optimized solution.

---

Problem Statement

Given two sorted linked lists, merge them into a single sorted linked list.

Example

Input:

List1: 1 -> 3 -> 5
List2: 2 -> 4 -> 6

Output:

1 -> 2 -> 3 -> 4 -> 5 -> 6

---

Approach 1: Recursive Solution

Idea

• Compare the head nodes of both lists.
• The smaller node becomes the head of the merged list.
• Recursively merge the remaining nodes.

Code

var mergeTwoLists = function(list1, 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;
    }
};

Complexity Analysis

• Time Complexity: O(n + m) (where n and m are the sizes of the two lists)
• Space Complexity: O(n + m) (due to recursive stack calls)

---

Approach 2: Iterative Solution (Optimized)

Idea

• Use a dummy node to simplify list operations.
• Use a pointer to iterate and merge nodes in-place.
• Attach any remaining nodes after traversal.

Code

var mergeTwoLists = function (list1, list2) {
    let res = new ListNode(0); // Dummy node
    let pointer = res;

    while (list1 !== null && list2 !== null) {
        if (list1.val <= list2.val) {
            pointer.next = list1;
            list1 = list1.next;
        } else {
            pointer.next = list2;
            list2 = list2.next;
        }
        pointer = pointer.next;
    }

    // Attach the remaining nodes
    pointer.next = list1 !== null ? list1 : list2;

    return res.next; // Skip dummy node
};

Complexity Analysis

• Time Complexity: O(n + m) (since each node is visited once)
• Space Complexity: O(1) (no extra space used except pointers)

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	In-Place
Recursive	O(n + m)	O(n + m) (due to recursion)	❌ No
Iterative	O(n + m)	O(1)	✅ Yes

Final Thoughts

• If recursion depth is a concern, prefer the iterative approach.
• The iterative approach is the most optimized as it avoids extra stack space.
• Both approaches run in O(n + m) time, which is optimal.

Hope this helps in understanding the problem and its solution! 🚀