Reorder List

Problem

You are given the head of a singly linked list. Reorder it to: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

Examples

The brute-force approach

Store all nodes in an array. Use two pointers (front and back) to interleave them and rebuild the list.

nodes = collect all nodes into an array
left, right = 0, len(nodes) - 1
while left < right:
    nodes[left].next = nodes[right]
    left++
    if left == right: break
    nodes[right].next = nodes[left]
    right--
nodes[left].next = None

O(n) time and O(n) space for the array.

Spotting the pattern

This is a Linked List problem. The key question to ask yourself:

After finding the middle and reversing the second half, how do you interleave the two halves without losing any next pointers?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.