Interleave two linked lists, taking nodes alternately starting with the first
list: a0, b0, a1, b1, …. When one list runs out, append the remainder of the
other. Return the head of the zipped list.
zipperLists(a, b)
Input format: listA | listB. Output the zipped list, space-separated.
(1 → 2 → 3) , (9 → 8 → 7) // → 1 → 9 → 2 → 8 → 3 → 7
(1 → 2 → 3 → 4) , (9) // → 1 → 9 → 2 → 3 → 4
(empty) , (5 → 6) // → 5 → 6
Zippering two lists means weaving them together, alternating sources, while reusing existing nodes rather than copying values. The real challenge isn't the alternation — it's building the result correctly when there's nowhere yet to attach the first node.
The very first append is awkward: there's no "previous node" to extend from. The fix: invent a placeholder node before the result even starts — the dummy head. Its next becomes "the start of the result so far," and a separate "tail" pointer always points at the last node attached. Every append, including the first, is the same operation: attach after the tail, move the tail forward. At the end, the real answer is the dummy's next — the dummy itself gets discarded.
With that scaffolding, alternation is simple: while both lists still have nodes, take the front of the first list and append it, advance; take the front of the second list and append it, advance. Repeating this two-step dance produces the interleaved order naturally.
The loop stops the moment either list runs out. At that point, either both lists were the same length and both are now empty, or exactly one still has nodes left. Since the loop requires both to be non-empty to continue, it's impossible for both to still have nodes when it ends — so whichever one isn't empty is exactly what you splice onto the tail wholesale. No need to interleave the leftover; there's nothing left to alternate with.
Since you're relinking existing nodes rather than copying values into new ones, no extra memory proportional to list length is needed beyond a handful of pointers — the input lists' own storage becomes the output's storage.
Every node from both lists is visited and relinked exactly once, so total work scales with their combined length — and there's no way to do better, since every node in the result must be touched at least once to be placed.
def zipper_lists(a, b):
dummy = ListNode(0)
tail = dummy
while a is not None and b is not None:
tail.next = a
a = a.next
tail = tail.next
tail.next = b
b = b.next
tail = tail.next
tail.next = a if a is not None else b
return dummy.next
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.