Solving Merge Two Sorted Lists - LeetCode problem

In the "Merge Two Sorted Lists" LeetCode problem, you'll encounter a common task in programming: merging two sorted linked lists into a single sorted list. This challenge tests your ability to work with linked data structures and efficiently combine them to maintain order.

Approach

1. First we need to find which is the eligible head among the 2 lists by comparing their values. Assign that to a head variable.

2. Traverse both the lists until either one of them becomes empty.

   1. Compare the list1 and list2 values and assign the temp.next variable accordingly

   2. Traverse the list using temp = temp.next

3. If either of the lists are still not empty then make the appropriate connection between temp.next and the rest of the list

4. Return head

Implementation

var mergeTwoLists = function(list1, list2) {
    if(list1 === null) return list2;
    if(list2 === null) return list1;
    let head = null;
    if(list1.val < list2.val) {
        head = list1;
        list1 = list1.next;
    } else {
        head = list2;
        list2 = list2.next;
    }
    let temp = head;
    while(list1 !== null && list2 !==null) {
        if(list1.val < list2.val) {
            temp.next = list1;
            list1 = list1.next;
        } else {
            temp.next = list2;
            list2 = list2.next;
        }
        temp = temp.next;
    }

    if(list1 !== null) {
        temp.next = list1;
    }
    if(list2 !== null) {
        temp.next = list2;
    }
    return head;
};

Time Complexity : O(N+M) where N is length of list1 and M is length of list2 
Space Complexity: O(1)

For an Input: list1 = [1,2,4], list2 = [1,3,4], 
this would be the final state:

head
|
v
1 -> 1 -> 2 -> 3 -> 4 -> 4
                         ^
                         |
                        temp