Linked Lists

Merging Lists

Merge or interleave sorted lists with a dummy tail.

Medium, about 60 minutes to practise.

1Understand

The idea

Keep a dummy head and a tail pointer, repeatedly attach the smaller of the two current nodes, and advance in that list. When one list runs out, attach the rest of the other in one step. Merging this way is O(n + m) and needs no extra nodes.

Intuition

Keep a dummy head and a tail pointer. Repeatedly attach the smaller of the two current nodes and advance in that list. When one list runs out, attach the rest of the other in one step.

Merging this way is O(n + m) and allocates no extra nodes, you only rewire. The same skeleton merges k lists when combined with a heap, or rebuilds a list after sort.

Dummy + tail means you never special-case "first node".

What you will be able to do

  • Use a dummy node
  • Attach the remaining tail

When to use it

  • Merge two sorted lists
  • Interleave or partition a list

2See it

Walkthrough

Merge two sorted lists

A = 1→3, B = 2→4, always take the smaller head.

1 / 6

LR
D
1
3
|
2
4
012345
L → index 1R → index 4

Dummy head D simplifies tail wiring. a=head of A(1→3), b=head of B(2→4).

dummy = ListNode(0); tail = dummy

Live template

Line 1 active

1dummy = tail = ListNode()
2while a and 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
6tail.next = a or b
7return dummy.next

Complexity: time O(n + m), space O(1)

Time O(n + m), space O(1) extra. Building a new list of fresh nodes is also fine but uses O(n + m) space. For k lists, heap merge is O(N log k); pairwise merge can be O(N log k) too depending on order.

Read the walkthrough as text

Merge two sorted lists. l1 = 1 → 2 → 4, l2 = 1 → 3 → 4.

  1. Dummy D, tail = D.
  2. Compare 1 vs 1: attach either (say from l1), advance that list.
  3. Continue: attach 1 (l2), 2, 3, 4, then the remaining 4.
  4. Result D.next is 1 → 1 → 2 → 3 → 4 → 4.

In code:

  • dummy = tail = ListNode(0)
  • while l1 and l2:
  • if l1.val <= l2.val:
  • tail.next, l1 = l1, l1.next
  • else:
  • tail.next, l2 = l2, l2.next
  • tail = tail.next
  • tail.next = l1 or l2
  • return dummy.next

3Recognise it

Kinds of problems (4)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Merge two sorted lists

    Example. Return head of merged sorted list.

    How. Dummy tail; each step attach smaller head; advance that list.

  • Partition around a value

    Example. All nodes < x before nodes ≥ x.

    How. Two dummy chains for less and greater; splice together at the end.

  • Reorder / interleave a list

    Example. L0 → Ln → L1 → Ln−1 → …

    How. Find middle, reverse second half, merge alternating nodes from both halves.

  • Sort a list with merge sort

    Example. Sort linked list in O(n log n).

    How. Find mid with fast/slow, recurse on halves, merge sorted pieces with dummy tail.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Remainder dropped

    Why it happens. Loop exits when one list is empty but the other still has nodes.

    How it fails. Merge stops at None, remaining 1→2→3 on list B is never attached.

    Fix. After the while loop: `tail.next = a or b` once.

  • Returns the dummy

    Why it happens. Returning the helper node instead of the real head.

    How it fails. return dummy, caller gets a node with no value instead of the merged chain.

    Fix. return dummy.next, dummy is only a write anchor.

  • Tail not advanced

    Why it happens. Linking without moving tail builds a self-loop or overwrites the same link.

    How it fails. tail.next = a repeatedly without tail = tail.next, every node points to the same first node.

    Fix. After each attach: `tail = tail.next`.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons