Reorder List

MEDIUM✓ CHIP-TIMEDLC #143 — FULL STATEMENT ↗

The drill: Weave the front half and the reversed back half of a linked list together — first node, last node, second node, second-to-last, and so on — rewiring the existing nodes in place instead of returning a new list.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A singly linked list arrives, and the job is to rewire it into a specific zigzag order: first node, then last node, then second node, then second-to-last, alternating inward from both ends until the nodes run out.

This rewiring happens in place, using the list's existing nodes — no new list gets built, and no array of values gets returned as the answer.

Odd-length lists leave one node stranded in the middle with no partner to pair with, and it simply stays put once the rest of the list has been woven around it.

EX 01

head = [1, 2, 3, 4]

→ [1, 4, 2, 3]

EX 02

head = [1, 2, 3, 4, 5]

→ [1, 5, 2, 4, 3]

EX 03

head = [-9, -7, -5, -3, -1]

→ [-9, -1, -7, -3, -5]

ALL-NEGATIVE, ODD LENGTH

list holds up to a few thousand nodes
reordering happens in place on the existing nodes, no new list built
an empty list or single node needs no reordering at all
odd-length lists leave their middle node unpaired

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Splitting into two arrays and interleaving them is honest but spends O(n) extra memory holding every node twice. What structural trick turns 'walk backward from the end' into something a singly linked list can actually do?

HINT 2 THE STRUCTURE

A reversed second half turns 'walk backward from the tail' into 'walk forward from a new head' — and reversal is a pointer-flip you already know how to do in place.

HINT 3 ONE STEP FROM THE ANSWER

Find the midpoint with slow/fast pointers, reverse everything after it in place, then zip the two halves together — one node from the front half, one from the reversed back half, alternating until they run out.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ZIGZAG WEAVEPATTERN · SPLIT, REVERSE, ZIPhead = 1 → 2 → 3 → 4 → 5

STEP 1

List 1 → 2 → 3 → 4 → 5. Find the midpoint, reverse the back half, then zip the two halves front-to-back.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/reorder-list.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return

        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        prev = None
        curr = second
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        first, second = head, prev
        while second:
            n1 = first.next
            n2 = second.next
            first.next = second
            if n1:
                second.next = n1
            first = n1
            second = n2

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 30 LN

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return
        nodes = []
        n = head
        while n:
            nodes.append(n)
            n = n.next

        i, j = 0, len(nodes) - 1
        while i < j:
            nodes[i].next = nodes[j]
            i += 1
            if i == j:
                break
            nodes[j].next = nodes[i]
            j -= 1
        nodes[i].next = None

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 19 LN

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode second = slow.next;
        slow.next = null;

        ListNode prev = null, curr = second;
        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }

        ListNode first = head;
        second = prev;
        while (second != null) {
            ListNode n1 = first.next;
            ListNode n2 = second.next;
            first.next = second;
            if (n1 != null) second.next = n1;
            first = n1;
            second = n2;
        }
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 33 LN

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) nodes.add(n);

        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i == j) break;
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        nodes.get(i).next = null;
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 17 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED