Oudom's site

Question Link: https://leetcode.com/problems/merge-two-sorted-lists/

Problem: Merge Two Sorted Lists

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.

Example 1:

merge-2-sortedlist-merge-ex1.jpg-

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Walkthrough + Thought process

We are dealing with 2 sorted linked lists here and we need to splice up the nodes to form a merged linked list.

Let’s think about solving this in simple English then transition to code itself

Coming up with the solution in words

We need to loop through both of list1 and list2 at the same time.
Keep track of the values of list1 and list2 when we go through the loop.
Compare the node value that it is on, if list1 is lesser than or equal to list2 then that node in list1 needs to come first.
After declaring which value is smaller from list1 and list2, point to the next node of the list, i.e. if list1 current node value is 1 and list2 current node value is 1, move the ‘current node’ of list1 to the next value.
Repeat.
If there are any left over values, in either list1 or list2, add it to the end of our merged linked list(as these values are greater and in order).

I believe that this question is one of those questions that are easier to see in code rather than in words so if you are a bit lost at the moment, don’t worry!

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {

    // Make a new dummy node and keep track of its value
    let dummy = new ListNode()
    let head = dummy

    // Loop through list if either list1 or list2 is null, stop the list
    while (list1 !== null && list2 !== null) {

        // if list1 value is less than or equals to list2 value then add it to our new linkedlist
        if (list1.val <= list2.val) {
            dummy.next = list1
            list1 = list1.next
        }
        
        // if list2 value is less than list1 value then add it to our new linkedlist
        else {
            dummy.next = list2
            list2 = list2.next
        }

        // for each iteration, keep track of the tail value, so that we can add the new nodes to it
        dummy = dummy.next
    }

    // if list1 is empty and list2 still has values then add list2 to the tail of our new linkedlist
    if (list1 === null) {
        dummy.next = list2
    }

    // else if list2 is empty and list1 still has values, add list1 to the tail of our new linkedlist instead
    else if (list2 === null) {
        dummy.next = list1
    }

    return head.next
    
};

Analysis

Time Complexity

We are looping through list1 and list2 once and this is the most time expensive operation in the code. This makes our time complexity O(n + m) . n is the size of list1 and m is the size of list2.

Space Complexity