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: enter image description here

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;
} 

• programoholic: this doesn't work at all! What if one of the list items gets empty ? and other still have items left?
• RoToRa: @programoholic What do you mean? They handle that case.
• greybeard: (I guess I don't "get" the 17:04 edit from revision 3 to revision 4.)