Merge Two Sorted Lists

Merging two sorted linked lists is a common problem in algorithmic coding interviews. The task is to merge the two lists into a single sorted list while maintaining the order of the elements. Although the problem may seem straightforward at first, there are multiple approaches that can be employed to tackle it, each with its own trade-offs in terms of time complexity and space complexity.

In this article, we will delve into different approaches to solve the merging of two sorted linked lists. Throughout the article, we will provide a detailed explanation of each approach, along with its time and space complexity analysis.

So without further ado let’s get started.

Problem Statement:

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

Merge the two lists in a 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.

Approach 1: Iterative solution

1. Create a dummy node and a pointer that will act as the merged list.

2. Iterate through both input lists simultaneously, comparing the values of the current nodes.

3. Append the smaller value to the merged list by moving the corresponding pointer forward.

4. Continue this process until one of the lists reaches its end (i.e., its value becomes null).

5. After reaching the end of one list, append all the remaining nodes from the other list to the merged list.

6. Finally, return the merged list by accessing dummy.next, which points to the head of the merged list.

// ES6 Arrow Function
const mergeTwoLists = (list1, list2) => {

    // dummy node and pointer 
    let dummy = new ListNode(0);
    let pointer = dummy;

    // compare values and add to the merged list
    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;
    }

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

    return dummy.next;
}

Time Complexity: O(N + M)

We are iterating through both the list once, and the length of the lists are n and m respectively. So time complexity is linearly proportional to the total number of node present in the lists.

Space Complexity: O(1)

We use a constant amount of extra space by creating a dummy node and the pointer. The merging is done in place without requiring any additional data structure.

Approach 2: Recursive

1. Base case: If either of the linked lists is empty, return the other list.

2. Compare the values of the heads of the two lists.

3. Set the smaller value as the head of the merged list.

4. Recursively call the function with the next node of the list that had the smaller value.

5. Set the next pointer of the merged list to the result of the recursive call.

6. Return the merged list.

// ES6 Arrow Function
const mergeTwoLists = (list1, 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;
    }

}

Time Complexity: O(N + M), where N and M are the lengths of two input-linked lists.

The recursive function is called for each node in both lists, and each call takes constant time. Therefore, the time complexity is linearly proportional to the total number of nodes in the input lists.

Space Complexity: O(N + M)

The recursive calls use the call stack, which grows with the number of recursive calls. In the worst case, when the lists are of equal length, the maximum depth of the call stack is N (or M).

And there you have it guys! We’ve explored two different approaches, saw their implementation in JavaScript, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 21