Merge Sorted LinkedList (Recursive)
Watch the walkthrough
Open on InstagramProblem
Merge two ascending singly linked lists recursively, returning the smaller head and merging its remainder with the other list.
Approach and revision checks
An empty list is the base case. Each call consumes one node, so time is O(m+n) and worst-case call-stack space is O(m+n). The supplied repository stores both merge versions in file 3; there is no separate file 4. The second definition is the recursive one. Test two empty lists, one empty list, and duplicate values. Very long lists can exceed the JavaScript call-stack limit.
Original repository source
Copied from the supplied local DSA-Series checkout; code and comments are preserved. Run alternative definitions separately when comparing approaches.
3-merge-sorted-linkedlist.js
// Merge the linked lists
// TC: O(M+N), SC: O(1)
var mergeTwoLists = function (list1, list2) {
const dummy = new ListNode();
let curr = dummy;
while (list1 && list2) {
if (list2.val <= list1.val) {
curr.next = list2;
list2 = list2.next;
} else {
curr.next = list1;
list1 = list1.next;
}
curr = curr.next;
}
curr.next = list1 || list2;
return dummy.next;
};
// Merge the linked lists - Recursive
// TC: O(M+N), SC: O(M+N) call stack space
var mergeTwoLists = function (list1, list2) {
if (!list1) return list2;
if (!list2) return list1;
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
};