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

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!