Weave two sorted chains into one

Linked lists Junior Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank to attach whatever is left.

Python 3.13
a, b, out = [1, 4, 9], [2, 3], []
i = j = 0
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        out.append(a[i])
        i += 1
    else:
        out.append(b[j])
        j += 1
out += ____
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A a[i:] + b[j:]

Right: one of the two slices is empty, and the other holds the sorted leftovers.

On a chain the same step is a single arrow, because the leftover part is already linked in order.

Why not the others?
  • B a + b. That repeats values already taken.
  • C sorted(a + b). It re-sorts everything and repeats values.

30-second answer

Start from a placeholder link and keep a tail pointer. At each step attach whichever head is smaller and advance that chain. When one chain runs out, attach the rest of the other in one move. O(n + m) time, O(1) extra memory.

Practise saying it · 30 s. No recording, just a timer

Explain weaving two sorted chains.

Say your answer out loud, then check which of these points you covered:

  • Placeholder and tail
  • Take the smaller head
  • Attach the leftover

Deep dive

Attaching the leftover chain in one step is what keeps the work linear and simple.

Taking from the left chain on ties keeps the merge stable.

This is the merge step of merge sort on chains, which sorts a chain in O(n log n) with no random access.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def weave(a: Link | None, b: Link | None) -> Link | None:
    front = Link(0)
    tail = front
    while a is not None and b is not None:
        if b.val < a.val:
            a, b = b, a  # keep the smaller head in a
        tail.next = a
        tail, a = a, a.next
    tail.next = a if a is not None else b  # the rest is in order
    return front.next

Common mistakes

  • Forgetting to attach the leftover links.
  • Losing the head by not using a placeholder.

Senior take & follow-ups

Mention stability (ties from the left) without being asked.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you merge k sorted chains?

    Show hint

    Keep the current head of each in a min-heap: O(N log k).

  2. How would you sort a chain?

    Show hint

    Split at the middle with slow and fast pointers, sort each half, weave them.

What each operation costs: Linked List · Singly Linked List · Doubly Linked List

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.