Merge Two Sorted Lists

07 Mar, 2021

Problem

Merge two sorted linked lists and return it as a sorted list. The 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.

My Solution

failed

const mergeTwoLists = (l1, l2) => {
	const mergedList = l1.concat(l2);
	return mergedList.sort((a, b) => a - b);
};

success

const mergeTwoLists = (l1, l2) => {
	if (!l1 || !l2) return l1 || l2;
	const val1 = l1.val;
	const val2 = l2.val;
	let mergedNode;
	if (val1 < val2) {
		mergedNode = new ListNode(val1);
		mergedNode.next = mergeTwoLists(l1.next, l2);
	} else {
		mergedNode = new ListNode(val2);
		mergedNode.next = mergeTwoLists(l2.next, l1);
	}
	return mergedNode;
};