21. Merge Two Sorted Lists

Solution

/**
 * 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) {
    // Edge case
    if (!list1) return list2;
    if (!list2) return list1;
    
    let f = list1;
    let s = list2;
    let root = new ListNode();
    const result = root;
    
    while (f && s) {
        if (f.val < s.val) {
            root.next = f;
            f = f.next;
        } else {
            root.next = s;
            s = s.next;
        }
        root = root.next;
    }
    
    // After loop only one element remains.
    if (f) {
        root.next = f;
    }
    if (s) {
        root.next = s;
    }
    
    return result.next;
};

Complexity

  • Time Complexity: O(N*M), where N and M are the size of the two lists.
  • Space Complexity: O(1), we are not using extra memory, just shifting pointers.

All Solutions