How do you merge two sorted linked lists into one sorted list?
Use a dummy head and a tail pointer. Repeatedly attach the smaller of the two current nodes to the tail and advance that list. When one list ends, attach the rest of the other.
Explain it simply
Two queues of students, each already sorted by roll number, need to become one queue. You look at the first student of each queue and send the smaller roll number into the new queue. Repeat until one queue is empty, then the remaining students simply follow.
A dummy node at the start saves you from writing special code for the first node.
Example
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function fromArray(arr) {
const dummy = new ListNode(0);
let tail = dummy;
for (const v of arr) {
tail.next = new ListNode(v);
tail = tail.next;
}
return dummy.next;
}
function toArray(head) {
const out = [];
while (head) {
out.push(head.val);
head = head.next;
}
return out;
}
function mergeTwoLists(a, b) {
const dummy = new ListNode(0);
let tail = dummy;
while (a && b) {
if (a.val <= b.val) {
tail.next = a;
a = a.next;
} else {
tail.next = b;
b = b.next;
}
tail = tail.next;
}
tail.next = a || b;
return dummy.next;
}
const merged = mergeTwoLists(fromArray([1, 3, 5]), fromArray([2, 4, 6, 8]));
console.log(toArray(merged)); // Output: [1,2,3,4,5,6,8]Complexity
Time O(n + m), space O(1).
What to say in the interview
"I walk both lists with a tail pointer behind a dummy head, always linking the smaller current node. When one list runs out I link the leftover of the other. It reuses the existing nodes, so it takes O(n + m) time and O(1) extra space."
Common mistakes
- Creating new nodes instead of relinking, which wastes memory.
- Forgetting to attach the remaining nodes after the loop.