LeetCode: [21] Merge Two Sorted Lists

2 minutes

February 10, 2023

Problem

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.

Example 1:

Alt text

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.

Solution


var mergeTwoLists = function(list1, list2) {

    // if either list is null we just
    // return the other

    if(!list1) return list2
    if(!list2) return list1

    let sorted = new ListNode()

    const first = sorted

    let l1pointer = list1
    let l2pointer = list2

    // loop while there is an element
    // in either list

    while(l1pointer || l2pointer) {

        // transverse list1 and keep moving to the next
        // position while the current value is less than
        // the next value in the other list

        while(l1pointer && (!l2pointer || l1pointer.val <= l2pointer.val)) {
            // we found the node that comes next
            // move our pointers to the next position
            sorted.next = l1pointer
            sorted = sorted.next
            l1pointer = l1pointer.next
        }

        // same as previous loop

        while(l2pointer && (!l1pointer || l2pointer.val < l1pointer.val) ) {
            sorted.next = l2pointer
            sorted = sorted.next
            l2pointer = l2pointer.next
        }

    }

    // return the first real node

    return first.next
}