Merge Two Sorted Lists in JavaScript

Question

The task is taken from LeetCode

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: l1 = [], l2 = [] 
Output: [] 

Example 3:

Input: l1 = [], l2 = [0] 
Output: [0]  

Constraints:

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

The following solutions are identical logically. They only differ in style:

Style 1

 /**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
    l2.next = mergeTwoLists(l2.next, l1);
    return l2;
};

Style 2

 /**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    if (!l1 || !l2) return l1 || l2; 
    const linkThem = (smaller, greater) => {
        smaller.next = mergeTwoLists(smaller.next, greater);
        return smaller;
    };
    return l1.val < l2.val ? linkThem(l1,l2) : linkThem(l2,l1);
};

Answer 1

Looks good!

• I would say maybe the following styles would be just a bit more readable, easier to follow.

• We can also alter l1 and l2 with more descriptive variable names.

Line Counting Fallacy:

• Sometimes, Line/character countings are helpful for command line languages/scripts (awk, grep, sed, regex, etc.) or maybe Code Golfing, is not a JavaScript practice though.

Iterative using a Sentinel Node

const mergeTwoLists = function(l1, l2) {
    const sentinel = {
        val: -1,
        next: null
    }

    let head = sentinel
    while (l1 && l2) {
        if (l1.val > l2.val) {
            head.next = l2
            l2 = l2.next
        } else {
            head.next = l1
            l1 = l1.next
        }
        
        head = head.next
    }

    head.next = l1 || l2

    return sentinel.next
}

---

Recursive

const mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2
    }

    if (l2 === null) {
        return l1
    }

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1

    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}

Or even better that those:

const mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    }

    if (l2 === null) {
        return l1;
    }

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1;

    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2;
    }
}

---

const mergeTwoLists = function(l1, l2) {
    const sentinel = {
        val: -1,
        next: null
    };

    let head = sentinel;
    while (l1 && l2) {
        if (l1.val > l2.val) {
            head.next = l2;
            l2 = l2.next;
        } else {
            head.next = l1;
            l1 = l1.next;
        }
        
        head = head.next;
    }

    head.next = l1 || l2;

    return sentinel.next;
}