Reorder List: Three Linked List Primitives in One Question

If you interview at Meta, Amazon, LinkedIn, expect some version of "Reorder List". It is rated Medium, and it falls squarely into the Fast and Slow Pointers pattern — pattern-first preparation beats grinding random problems every time. Part 7 of 11 in the Fast and Slow Pointers arc.

The Problem

Given a list L0 -> L1 -> ... -> Ln, reorder it in place to L0 -> Ln -> L1 -> Ln-1 -> L2 -> ... — values may not be modified, only node pointers. This is a composition test: midpoint, reversal, and interleaved merge, each of which must work on the first try.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 5 -> 2 -> 4 -> 3

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

The target order alternates front and back of the original — you need simultaneous forward and backward iteration, which on a singly linked list means: split at the middle (fast and slow), reverse the back half, then zip. The pattern is the first third of the solution.

The Approach

Find the middle with the first-middle loop condition, cut the list in two, and reverse the second half. Then merge alternately: one from the front half, one from the reversed back half. The front half is always equal in length or one longer, so the merge loop runs on the second list.

Severing the halves (slow.next = None after saving the successor) is the step people forget — without it the merge chases a tail that still points into itself.

Python Solution

class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val = val
        self.next = next


def reorder_list(head: ListNode | None) -> None:
    """Reorder in place to L0, Ln, L1, Ln-1, ... Mutates the list."""
    if not head or not head.next:
        return

    slow, fast = head, head
    while fast.next and fast.next.next:   # slow -> first middle
        slow = slow.next
        fast = fast.next.next

    second = slow.next
    slow.next = None                       # sever the halves
    prev = None
    while second:                          # reverse back half
        second.next, prev, second = prev, second, second.next

    first = head
    while prev:                            # interleave
        first.next, prev.next, first, prev = prev, first.next, first.next, prev.next

Complexity

• Time: O(n) — three linear phases
• Space: O(1) — pointer surgery only

Interview Tips and Follow-Ups

• The multi-target tuple assignment in the merge is compact but fragile — expand it into named temporaries when whiteboarding.
• Each sub-step is its own interview question; practice them isolated (reverse a list cold, in under two minutes) before composing.
• Copying values into an array and rewriting is O(n) space and usually rejected — but stating it first buys thinking time legitimately.

If this clicked, continue the Fast and Slow Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.