Fold a chain: first, last, second, second-last

Linked lists Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
vals = [1, 2, 3, 4, 5, 6]
half = (len(vals) + 1) // 2
front, back = vals[:half], vals[half:][::-1]
out = []
for i, v in enumerate(front):
    out.append(v)
    if i < len(back):
        out.append(back[i])
print(out)

Options

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

Show answer

Answer: A [1, 6, 2, 5, 3, 4]

Right: the front half alternates with the turned-around back half.

The list version shows the target shape; the chain version reaches it with the same split, turn and interleave steps without copying.

Why not the others?
  • B [1, 4, 2, 5, 3, 6]. The back half has to be turned around first.
  • C [6, 1, 5, 2, 4, 3]. The first link stays first.

30-second answer

Three steps, each O(n): find the middle with slow and fast pointers, turn the second half around, then interleave the two halves one link at a time. Total O(n) time and O(1) memory.

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

Explain folding a chain in place.

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

  • Find the middle
  • Turn the second half around
  • Interleave

Deep dive

It combines three templates (middle, turn around, weave), which is why interviewers like it.

Copying the links into a list and rewiring by index is O(n) memory but much easier; offer it as a first version.

Cut the first half's tail off before interleaving, or you create a loop.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def fold(head: Link | None) -> None:
    if head is None:
        return
    slow, fast = head, head.next
    # fast moves two links per step, slow one
    while fast and fast.next:
        slow = slow.next or slow
        fast = fast.next.next
    second, slow.next = slow.next, None  # cut after the middle
    back: Link | None = None
    while second is not None:
        second.next, back, second = back, second, second.next
    first: Link | None = head
    while first is not None and back is not None:
        after_first, after_back = first.next, back.next
        first.next, back.next = back, after_first
        first, back = after_first, after_back

Common mistakes

  • Not cutting the chain at the middle, which leaves a loop.
  • Splitting at the wrong middle for even lengths.

Senior take & follow-ups

Name the three steps before coding; it shows you can compose patterns.

Follow-up questions

Think of your answer first, then open the hint.

  1. What is the result for an even length, such as 1-2-3-4?

    Show hint

    1-4-2-3.

  2. Can you do it with recursion?

    Show hint

    Yes, by carrying a pointer from the front while unwinding from the back, but it uses O(n) stack.

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.