→ [0]
dummy
Given two sorted linked lists, weave them into one sorted list by repeatedly plucking the smaller front node — a dummy head eliminates all edge cases and lets tail.next = … do all the work.
You receive two singly-linked lists, each already sorted in non-decreasing order. Return the head of one merged sorted list built from the nodes of both. Example: 1→2→4 and 1→3→4 produce 1→1→2→3→4→4. Both lists may be empty; an empty list merged with any list returns that list unchanged.
const dummy = new ListNode(0), every attachment is identical: tail.next = chosen; tail = tail.next. The real head of the result is always dummy.next. This "sentinel" pattern appears throughout linked-list problems.dummy = new ListNode(0), tail = dummy. We never touch dummy.val.tail.next = winner; winner = winner.next; tail = tail.next.tail.next = list1 ?? list2. No need to walk it node by node.dummy.next. Skip the sentinel. If both inputs were empty, dummy.next is null, which is correct.tailafter the attachment. The loop does two things per iteration: attach and advance. Write tail = tail.next! as the last line inside the loop — if you try to do it at the start of the next iteration, you lose track of where to attach next.The merge can also be written recursively: list1.val ≤ list2.val ? (list1.next = merge(list1.next, list2), list1) : …. Elegant but uses O(m + n) stack frames — fine for an interview, risky in production for very long lists.
dummy head node (value 0). tailstarts at dummy. We'll always append to tail.next — this avoids special-casing the first node.// Definition: class ListNode { val: number; next: ListNode | null; ... }
function mergeTwoLists(
list1: ListNode | null,
list2: ListNode | null,
): ListNode | null {
const dummy = new ListNode(0); // sentinel avoids special-casing the head
let tail: ListNode = dummy;
while (list1 !== null && list2 !== null) {
if (list1.val <= list2.val) {
tail.next = list1;
list1 = list1.next;
} else {
tail.next = list2;
list2 = list2.next;
}
tail = tail.next!; // advance tail to the node just attached
}
// At most one list still has nodes — splice the remainder directly
tail.next = list1 ?? list2;
return dummy.next; // skip the sentinel
}dummy is a throw-away node whose only purpose is to give tail somewhere to live before the first real node is attached. Its value is never read.tail.next. We advance the source pointer (not tail) first, then advance tail last. This order keeps the rest of each source list accessible.list1 ?? list2splices the entire remaining sublist in O(1) because it's already sorted and we just need to point at its head.dummy.next. The sentinel sits one step before the real head. Returning dummy.next skips it. If both inputs were null, this returns null automatically.dummy node and the tail pointer are allocated; nodes are re-linked, not copied.null; otherwise compare heads and recurse on the winner's next. O(m + n) stack depth is the trade-off.≤ is a common convention that preserves the relative order of equal-valued nodes from list1 (stable merge).| merge two sorted linked lists | dummy head + tail pointer |
| "build a linked list from scratch" | dummy sentinel to avoid head special-case |
| one list exhausted before the other | splice remainder with tail.next = rest |
| merge k sorted lists | same pattern + min-heap for the k-way comparison |
function mergeTwoLists(
list1: ListNode | null,
list2: ListNode | null,
): ListNode | null {
const dummy = new ListNode(0);
let tail = dummy;
while (list1 && list2) {
if (list1.val <= list2.val) { tail.next = list1; list1 = list1.next; }
else { tail.next = list2; list2 = list2.next; }
tail = tail.next!;
}
tail.next = list1 ?? list2;
return dummy.next;
}tail starts there. Every attachment is uniform — no special case for the first node. Return dummy.next at the end.dummy.next instead of dummy?list1 = [1,2,4], list2 = [1,3,4]. What does the merge produce?