Merge patterns build one result list by walking sources with a dummy head + tail pointer.
Focus on recognizing:
“Sorted inputs” → pick smaller, advance. “K lists” → divide & conquer or heap.
Pattern 1: Merge Two Sorted Lists
[1,3,5] and [2,4] interleave into one sorted chain — the leftover list gets spliced whole. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list — compare an iterative dummy-head build against a recursive version.
Keep a dummy head and a tail; while both lists still have nodes, append the smaller front and advance it. At the end splice the leftover list in one move.
1
dummy → new node; tail = dummy
2
while a && b:
3
if a.val <= b.val: tail.next = a; a = a.next
4
else: tail.next = b; b = b.next
5
tail = tail.next
6
tail.next = a ?? b // splice the leftover
1
merge(a, b):
2
if a == null: return b
3
if b == null: return a
4
if a.val <= b.val:
5
a.next = merge(a.next, b); return a
6
else:
7
b.next = merge(a, b.next); return b
public ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b; // splice the rest
return dummy.next;
}def merge_two_lists(a, b):
dummy = tail = ListNode(0)
while a and 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 or b # splice the rest
return dummy.nextListNode* mergeTwoLists(ListNode* a, ListNode* b) {
ListNode dummy(0), *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 ? a : b; // splice the rest
return dummy.next;
}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; // splice the rest
return dummy.next;
}Dummy head removes the empty-result special case;
tailis the write cursor.
Pattern 2: Merge K Sorted Lists
Pair lists up recursively — each merge halves the count, O(N log k) total. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Merge K Sorted Lists
Merge k sorted linked lists into one sorted list.
Keep a min-heap of the current head of each list. Repeatedly pop the smallest node, append it, and push its successor. Each of the N total nodes costs O(log k) for a heap operation.
1
heap = heads of all lists
2
while heap:
3
pop min node → append to output
4
push its .next if any
Pair up lists recursively — k merges of halves, O(N log k):
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
int interval = 1;
while (interval < lists.length) {
for (int i = 0; i + interval < lists.length; i += interval * 2)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
interval *= 2;
}
return lists[0];
}def merge_k_lists(lists):
if not lists:
return None
interval = 1
while interval < len(lists):
for i in range(0, len(lists) - interval, interval * 2):
lists[i] = merge_two_lists(lists[i], lists[i + interval])
interval *= 2
return lists[0]ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
int interval = 1;
while (interval < (int)lists.size()) {
for (int i = 0; i + interval < (int)lists.size(); i += interval * 2)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
interval *= 2;
}
return lists.empty() ? nullptr : lists[0];
}function mergeKLists(lists) {
if (!lists.length) return null;
let interval = 1;
while (interval < lists.length) {
for (
let i = 0;
i + interval < lists.length;
i += interval * 2
)
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
interval *= 2;
}
return lists[0];
}Merging one-against-all is O(k·N); pairing halves is O(N log k). Same code, better order.
Pattern 3: Add Two Numbers
Digit-wise addition with carry — reversed order makes it trivial. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Add Two Numbers
Add two numbers represented as reversed digit-linked lists, returning the sum as a new list.
Walk both lists digit by digit with a carry, appending sum%10 each step and propagating carry/10. Reversed storage means the ones digit is first, so no alignment is needed; a trailing carry just appends one node.
1
carry = 0
2
while a or b or carry:
3
s = (a?.val||0) + (b?.val||0) + carry
4
append s % 10; carry = s / 10 | 0
Digits stored in reverse; sum with carry:
public ListNode addTwoNumbers(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
int carry = 0;
while (a != null || b != null || carry > 0) {
int sum = carry;
if (a != null) { sum += a.val; a = a.next; }
if (b != null) { sum += b.val; b = b.next; }
carry = sum / 10;
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
return dummy.next;
}def add_two_numbers(a, b):
dummy = tail = ListNode(0)
carry = 0
while a or b or carry:
total = carry
if a:
total += a.val
a = a.next
if b:
total += b.val
b = b.next
carry, digit = divmod(total, 10)
tail.next = ListNode(digit)
tail = tail.next
return dummy.nextListNode* addTwoNumbers(ListNode* a, ListNode* b) {
ListNode dummy(0), *tail = &dummy;
int carry = 0;
while (a || b || carry) {
int sum = carry;
if (a) { sum += a->val; a = a->next; }
if (b) { sum += b->val; b = b->next; }
carry = sum / 10;
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
return dummy.next;
}function addTwoNumbers(a, b) {
const dummy = new ListNode(0);
let tail = dummy,
carry = 0;
while (a || b || carry) {
let sum = carry;
if (a) {
sum += a.val;
a = a.next;
}
if (b) {
sum += b.val;
b = b.next;
}
carry = Math.floor(sum / 10);
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
return dummy.next;
}The loop condition includes
carry > 0— that’s what creates the final extra node on overflow (99 + 1).
Common Mistakes
Losing nodes when splicing the remainder.
After the main loop, attach whichever list still has nodes — don’t rebuild it.
Forgetting the dummy node.
Special-casing the first merge step doubles the code and invites bugs.
Dropping the final carry.
carry > 0 must be part of the add-two-numbers loop condition.
Complexity
| Operation | Time | Space |
|---|---|---|
| Merge two | O(n + m) | O(1) |
| Merge k (pairwise) | O(N log k) | O(1) |
| Add numbers | O(max(n, m)) | O(max(n, m)) output |
Premium Content
Unlock Merge Two Lists and all premium lessons with a subscription.
From ₹199.99/year — See plans