Merge Sorted LinkedList (Iterative)
Watch the walkthrough
Open on InstagramProblem
Merge two ascending singly linked lists by relinking their existing nodes. Return the head of the merged list.
Approach and revision checks
The iterative version uses a dummy head and advances the smaller head pointer. O(m+n) time, O(1) auxiliary space. The original file also includes the recursive alternative with the same variable name; running the whole file leaves that last definition active. Run the iterative definition independently for this lesson. Both versions mutate the input links. Supply a ListNode constructor or use the judge's definition.
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;
}
};