Merge Two Sorted Lists (Leetcode 21)

• Leetcode 21
• Video Walkthrough

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.

Approach

1. Create a new node called tempNode and set its value to 0 and its next pointer to null.
2. Set currentNode to tempNode.
3. While l1 and l2 are not null, compare the values of the nodes pointed to by l1 and l2. Add the smaller value node to currentNode and move the corresponding pointer to its next node.
4. Set the next pointer of currentNode to the remaining nodes of l1 or l2.
5. Return the merged list starting from the next node of tempNode, which is tempNode.next.

Complexity

The time complexity of the iterative approach is O(m + n), where m and n are the lengths of l1 and l2, respectively. This is because we iterate over both lists once and compare each node at most once.

The space complexity of the iterative approach is O(1), since we only create a constant number of new nodes (tempNode and currentNode) and modify the pointers of the input lists in place. Therefore, the space required is constant and does not depend on the length of the input lists.

Code

const mergeTwoLists = (list1, list2) => {
    const dummyNode = {};
    let currentNode = dummyNode;

    // while both lists still have items
    while (list1 && list2) {
        // if list1 val is smaller
        if (list1.val < list2.val) {
            // set list1 as next
            currentNode.next = list1;
            // then set list1 to the next item 
            list1 = list1.next;
        } else {
            // else list2 val is smaller... set list 2 as next
            currentNode.next = list2;
            // then set list2 to the next item 
            list2 = list2.next;
        }
        // set current node to next input
        currentNode = currentNode.next;
    }

    // add on the remaining items from whichever list still has items
    currentNode.next = list1 || list2;

    return dummyNode.next;
};

const example1List1 = { val: 1, next: { val: 2, next: { val: 4 } } };
const example1List2 = { val: 1, next: { val: 3, next: { val: 4 } } };

const example2List1 = { };
const example2List2 = { };

const example3List1 = { };
const example3List2 = { val:0 };

console.log("example1", mergeTwoLists(example1List1, example1List2)); // [1,1,2,3,4,4] -> {  "val": 1, "next": { "val": 1, "next": { "val": 2, "next": { "val": 3, "next": { "val": 4, "next": { "val": 4 } } } } } }
console.log("example2", mergeTwoLists(example2List1, example2List2)); // [] 
console.log("example3", mergeTwoLists(example3List1, example3List2)); // [0]