You're given the heads of two singly linked lists, each already sorted in ascending order. Implement linkedListCombineTwoSorted(a, b) so it weaves them into a single ascending-sorted list and returns its head. Each node is a plain object of the shape { val, next }, where next points at the following node or is null at the end of the list. This is the classic merge step that sits at the heart of merge sort — given two sorted runs, produce one.
// A node is a plain object: { val: number, next: Node | null }.
// a, b: Node | null — the heads of two ascending-sorted lists (null = empty).
// returns: Node | null — the head of one ascending-sorted list (null if both empty).
function linkedListCombineTwoSorted(a, b): Node | null;// a: 1 -> 3 -> 5, b: 2 -> 4 -> 6 (shown as arrays for brevity)
linkedListCombineTwoSorted(list([1, 3, 5]), list([2, 4, 6]));
// → 1 -> 2 -> 3 -> 4 -> 5 -> 6// Duplicate values across both lists are all kept.
linkedListCombineTwoSorted(list([1, 1, 2]), list([1, 3]));
// → 1 -> 1 -> 1 -> 2 -> 3{ val, next }. The list ends when a node's next is null. There is no separate ListNode class — just these plain objects.a and b arrive in ascending order. Lean on that — you do not need to sort anything from scratch.null. If one is empty, return the other; if both are empty, return null.next pointers to splice nodes together, but leave each node's val alone.You'll walk both sorted lists at once with two cursors, and at each step pull off whichever current node holds the smaller value, building one merged chain as you go.
Picture two stacks of exam papers, each already sorted by score, lowest on top. You want one combined stack in score order. You don't re-sort everything — you just peek at the top of each stack, take whichever card is smaller, and drop it onto the new pile. Repeat until one stack runs dry, then drop the rest of the other stack on top as-is. Merging two sorted linked lists is that exact move: the lists arrive sorted, so you never compare more than the two front nodes at a time.
Keep two cursors, one parked on the front of each list. Compare the two vals, splice the smaller node onto the end of your result, and advance only the cursor you just took from. The other cursor stays put — its node hasn't been used yet. Because both inputs are sorted, the smaller of the two fronts is always the smallest value left anywhere, so taking it is always safe. When one list empties, the other is already sorted, so you attach the whole remaining tail in one move.
A common first instinct ignores that the lists are already sorted: collect every value into an array, sort it, and rebuild a list from the sorted array.
function linkedListCombineTwoSorted(a, b) {
const values = [];
for (let node = a; node !== null; node = node.next) values.push(node.val);
for (let node = b; node !== null; node = node.next) values.push(node.val);
values.sort((x, y) => x - y); // re-sorts everything from scratch
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = { val: values[i], next: head }; // a brand-new node per value
}
return head;
}This returns the right answer, but it throws away the one fact that makes the problem easy. The inputs are already sorted, yet we re-sort the combined values at O((n + m) log(n + m)) cost. It also allocates a fresh node for every value instead of reusing the nodes we were handed. We're doing a general sort when a single linear pass would do.
function linkedListCombineTwoSorted(a, b) {
// A dummy head lets us attach the first node the same way as every other
// node, so there's no special case for "is this the start of the list?".
// `tail` always points at the last node we've committed to the result.
const dummy = { val: 0, next: null };
let tail = dummy;
// While BOTH lists still have a node, splice whichever current node is
// smaller onto the tail, then advance only that list.
while (a !== null && b !== null) {
if (a.val <= b.val) {
tail.next = a; // reuse the existing node — no allocation
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
// One list is now empty. The other is already sorted, so attach it whole.
tail.next = a !== null ? a : b;
// dummy.next is the real head; if both inputs were empty it's still null.
return dummy.next;
}
module.exports = { linkedListCombineTwoSorted };Two ideas carry the fix. The first is the dummy head: a throwaway node that sits in front of the result so attaching the very first real node looks identical to attaching the tenth — you never write an if (result === null) special case. The second is the single linear pass: because both lists are sorted, comparing the two front vals and taking the smaller is enough; there's no global sort and no new allocation beyond the one dummy. The <= (not <) in the comparison means that when the two fronts tie, we take from a first, which keeps equal values in a stable, predictable order.
Trace linkedListCombineTwoSorted(1 -> 3 -> 5, 2 -> 4 -> 6).
dummy is a fresh node and tail points at it. Both lists are non-empty, so we enter the loop.
a: 1 -> 3 -> 5 b: 2 -> 4 -> 6 merged: dummy
compare 1 vs 2 → 1 <= 2, take a → tail.next = (1); a = 3 -> 5; tail = (1)
compare 3 vs 2 → 3 > 2, take b → tail.next = (2); b = 4 -> 6; tail = (2)
compare 3 vs 4 → 3 <= 4, take a → tail.next = (3); a = 5; tail = (3)
compare 5 vs 4 → 5 > 4, take b → tail.next = (4); b = 6; tail = (4)
compare 5 vs 6 → 5 <= 6, take a → tail.next = (5); a = null; tail = (5)
a is null → loop ends. Attach the rest of b: tail.next = (6).
return dummy.next → 1 -> 2 -> 3 -> 4 -> 5 -> 6
The last step is the payoff for sorted inputs: once a runs out, b is still 6 and everything after it is already in order, so we hang the whole remainder off the tail in one assignment rather than looping through it.
tail.next on every other one. That if (head === null) check is easy to get subtly wrong; the dummy node erases the special case entirely. Return dummy.next, never dummy.dummy instead of dummy.next. The dummy's val of 0 is not part of the answer. If you return dummy, you ship a phantom leading 0. The real head is always dummy.next.tail.next = a !== null ? a : b, you silently drop the remainder of the longer list. Because the leftover is already sorted, attaching it whole is correct — no further looping needed.< instead of <= on ties. Both produce a sorted list, but < flips the order of equal values between the lists on each tie. <= consistently takes from a first, which keeps duplicates in a stable, predictable order — handy when nodes carry more than just val.tail.next = a); don't { val: a.val, next: ... } your way to a fresh copy. The only new node is the dummy, and it's discarded on return.k sorted lists, merge them all. Folding this two-list merge across the array works but is O(k·n); a min-heap of the k front nodes, or pairwise merging in a tournament, gets you to O(n log k).next to the merge of the rest. It's elegant on paper but uses O(n + m) call-stack depth, which can overflow on long lists — the iterative loop here is the safer default.>= and you build a descending list instead. The shape of the algorithm doesn't change — only which front you call "smaller" does.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're given the heads of two singly linked lists, each already sorted in ascending order. Implement linkedListCombineTwoSorted(a, b) so it weaves them into a single ascending-sorted list and returns its head. Each node is a plain object of the shape { val, next }, where next points at the following node or is null at the end of the list. This is the classic merge step that sits at the heart of merge sort — given two sorted runs, produce one.
// A node is a plain object: { val: number, next: Node | null }.
// a, b: Node | null — the heads of two ascending-sorted lists (null = empty).
// returns: Node | null — the head of one ascending-sorted list (null if both empty).
function linkedListCombineTwoSorted(a, b): Node | null;// a: 1 -> 3 -> 5, b: 2 -> 4 -> 6 (shown as arrays for brevity)
linkedListCombineTwoSorted(list([1, 3, 5]), list([2, 4, 6]));
// → 1 -> 2 -> 3 -> 4 -> 5 -> 6// Duplicate values across both lists are all kept.
linkedListCombineTwoSorted(list([1, 1, 2]), list([1, 3]));
// → 1 -> 1 -> 1 -> 2 -> 3{ val, next }. The list ends when a node's next is null. There is no separate ListNode class — just these plain objects.a and b arrive in ascending order. Lean on that — you do not need to sort anything from scratch.null. If one is empty, return the other; if both are empty, return null.next pointers to splice nodes together, but leave each node's val alone.You'll walk both sorted lists at once with two cursors, and at each step pull off whichever current node holds the smaller value, building one merged chain as you go.
Picture two stacks of exam papers, each already sorted by score, lowest on top. You want one combined stack in score order. You don't re-sort everything — you just peek at the top of each stack, take whichever card is smaller, and drop it onto the new pile. Repeat until one stack runs dry, then drop the rest of the other stack on top as-is. Merging two sorted linked lists is that exact move: the lists arrive sorted, so you never compare more than the two front nodes at a time.
Keep two cursors, one parked on the front of each list. Compare the two vals, splice the smaller node onto the end of your result, and advance only the cursor you just took from. The other cursor stays put — its node hasn't been used yet. Because both inputs are sorted, the smaller of the two fronts is always the smallest value left anywhere, so taking it is always safe. When one list empties, the other is already sorted, so you attach the whole remaining tail in one move.
A common first instinct ignores that the lists are already sorted: collect every value into an array, sort it, and rebuild a list from the sorted array.
function linkedListCombineTwoSorted(a, b) {
const values = [];
for (let node = a; node !== null; node = node.next) values.push(node.val);
for (let node = b; node !== null; node = node.next) values.push(node.val);
values.sort((x, y) => x - y); // re-sorts everything from scratch
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = { val: values[i], next: head }; // a brand-new node per value
}
return head;
}This returns the right answer, but it throws away the one fact that makes the problem easy. The inputs are already sorted, yet we re-sort the combined values at O((n + m) log(n + m)) cost. It also allocates a fresh node for every value instead of reusing the nodes we were handed. We're doing a general sort when a single linear pass would do.
function linkedListCombineTwoSorted(a, b) {
// A dummy head lets us attach the first node the same way as every other
// node, so there's no special case for "is this the start of the list?".
// `tail` always points at the last node we've committed to the result.
const dummy = { val: 0, next: null };
let tail = dummy;
// While BOTH lists still have a node, splice whichever current node is
// smaller onto the tail, then advance only that list.
while (a !== null && b !== null) {
if (a.val <= b.val) {
tail.next = a; // reuse the existing node — no allocation
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
// One list is now empty. The other is already sorted, so attach it whole.
tail.next = a !== null ? a : b;
// dummy.next is the real head; if both inputs were empty it's still null.
return dummy.next;
}
module.exports = { linkedListCombineTwoSorted };Two ideas carry the fix. The first is the dummy head: a throwaway node that sits in front of the result so attaching the very first real node looks identical to attaching the tenth — you never write an if (result === null) special case. The second is the single linear pass: because both lists are sorted, comparing the two front vals and taking the smaller is enough; there's no global sort and no new allocation beyond the one dummy. The <= (not <) in the comparison means that when the two fronts tie, we take from a first, which keeps equal values in a stable, predictable order.
Trace linkedListCombineTwoSorted(1 -> 3 -> 5, 2 -> 4 -> 6).
dummy is a fresh node and tail points at it. Both lists are non-empty, so we enter the loop.
a: 1 -> 3 -> 5 b: 2 -> 4 -> 6 merged: dummy
compare 1 vs 2 → 1 <= 2, take a → tail.next = (1); a = 3 -> 5; tail = (1)
compare 3 vs 2 → 3 > 2, take b → tail.next = (2); b = 4 -> 6; tail = (2)
compare 3 vs 4 → 3 <= 4, take a → tail.next = (3); a = 5; tail = (3)
compare 5 vs 4 → 5 > 4, take b → tail.next = (4); b = 6; tail = (4)
compare 5 vs 6 → 5 <= 6, take a → tail.next = (5); a = null; tail = (5)
a is null → loop ends. Attach the rest of b: tail.next = (6).
return dummy.next → 1 -> 2 -> 3 -> 4 -> 5 -> 6
The last step is the payoff for sorted inputs: once a runs out, b is still 6 and everything after it is already in order, so we hang the whole remainder off the tail in one assignment rather than looping through it.
tail.next on every other one. That if (head === null) check is easy to get subtly wrong; the dummy node erases the special case entirely. Return dummy.next, never dummy.dummy instead of dummy.next. The dummy's val of 0 is not part of the answer. If you return dummy, you ship a phantom leading 0. The real head is always dummy.next.tail.next = a !== null ? a : b, you silently drop the remainder of the longer list. Because the leftover is already sorted, attaching it whole is correct — no further looping needed.< instead of <= on ties. Both produce a sorted list, but < flips the order of equal values between the lists on each tie. <= consistently takes from a first, which keeps duplicates in a stable, predictable order — handy when nodes carry more than just val.tail.next = a); don't { val: a.val, next: ... } your way to a fresh copy. The only new node is the dummy, and it's discarded on return.k sorted lists, merge them all. Folding this two-list merge across the array works but is O(k·n); a min-heap of the k front nodes, or pairwise merging in a tournament, gets you to O(n log k).next to the merge of the rest. It's elegant on paper but uses O(n + m) call-stack depth, which can overflow on long lists — the iterative loop here is the safer default.>= and you build a descending list instead. The shape of the algorithm doesn't change — only which front you call "smaller" does.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.