A support console stores a ticket’s messages as a singly linked list in send order. Product wants the thread pane to fold: opening message, latest reply, second message, second-to-last — so the agent sees how the ticket started and how it currently stands, then works inward. The intern copied every node into an ArrayList and rewrote next from both ends. A dozen-message staging ticket rendered. A bot-loop ticket with thousands of nodes allocated a second array of references; an even-length thread left a cycle and the renderer never returned.

Reorder List folds L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → … in place. The head does not move — L0 stays first — so the method is void. You mutate next on the nodes you were given.

This is an interview writeup, not a layout lecture. The linked list post owns splice and why get(i) walks. The two pointers post owns the slow/fast move rule. The work here is a composition: find a middle, reverse the back half, then zipper the two halves. That last splice is not the sorted merge in Merge Two Sorted Lists.

The problem

Given the head of a singly linked list, reorder it in place from L0 → L1 → … → Ln-1 → Ln into L0 → Ln → L1 → Ln-1 → …. Do not return a new list. Even and odd length are both legal. A one-node list is already folded.

1 → 2 → 3 → 4 → null          →  1 → 4 → 2 → 3 → null
1 → 2 → 3 → 4 → 5 → null      →  1 → 5 → 2 → 4 → 3 → null
1 → null                      →  1 → null
1 → 2 → null                  →  1 → 2 → null

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new next links. Copying values into an array and building a fresh chain passes a value-order test and fails any test that identity of nodes matters — the same trap Reverse Linked List already named. The brute below keeps the node objects and still spends O(n) extra space on an indexable list of them.

Copy the nodes, fold from both ends

Walk once, store every node in an ArrayList, then rewrite next from both ends the way you would on an array. The order is right. You paid random access you did not have.

void reorderListCopy(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    for (ListNode n = head; n != null; n = n.next) {
        nodes.add(n);
    }
    int i = 0;
    int j = nodes.size() - 1;
    while (i < j) {
        nodes.get(i).next = nodes.get(j);
        i++;
        nodes.get(j).next = nodes.get(i);
        j--;
    }
    nodes.get(i).next = null;
}

The last write is not optional. After the loop, the node under i is the last node of the fold; its old next still points somewhere in the original chain (or at its zipper partner). Leave it and you have a cycle.

At a handful of messages this is a rounding error. In production you paid O(n) extra space for a question three walks already answer in O(1) besides a few locals: cut the list, reverse the back half, zipper the two chains.

Cut the first-half tail, reverse, zipper

Three steps. None of them is new. The trap is which node you treat as the middle, and which merge you reach for.

  1. First-half tail. Middle of the Linked List parks slow on the second middle when the length is even. Paste that loop here and slow sits on node 3 in 1 → 2 → 3 → 4 — the head of the second half — with no handle on the node before it. For this prompt you need the last node of the first half so you can cut. Same 2:1 ratio; stop one step earlier: loop while fast.next and fast.next.next are both non-null. On odd length that still lands on the single middle (it stays with the first half). On even length it lands on the first middle, which is the cut point.
  2. Cut, then reverse. Set slow.next = null. Reverse the detached second half with the same three-pointer rewire Reverse Linked List already taught. Do not re-derive it.
  3. Zipper, not sorted merge. Merge Two Sorted Lists always splices the smaller current node by value. This splice ignores values: take one from the first half, one from the reversed second, repeat. No dummy. head is already L0.

Walk even length 1 → 2 → 3 → 4 — this is the length that cycles if you skip the cut:

first-half tail:
  start:  slow=1  fast=1
  step 1: slow=2  fast=3     fast.next.next is null, stop

cut:  1 → 2 → null     second = 3 → 4
reverse second:         4 → 3 → null

zipper:
  1.next = 4, 4.next = 2     1 → 4 → 2 → null     (2.next already null)
  2.next = 3, 3.next = null  1 → 4 → 2 → 3 → null

Skip the cut and 2 still points at 3. Reverse turns 3 → 4 into 4 → 3 (3.next is null, but 2.next is still 3). Zipper writes 1.next = 4 and 4.next = 2, then saves firstNext = 2.next — still 3 — and sets 3.next = firstNext. Node 3 points at itself. The renderer follows 3 → 3 → … forever.

Odd length 1 → 2 → 3 → 4 → 5 keeps the middle on the first half:

first-half tail:
  start:  slow=1  fast=1
  step 1: slow=2  fast=3
  step 2: slow=3  fast=5     fast.next is null, stop

cut:  1 → 2 → 3 → null     second = 4 → 5
reverse second:            5 → 4 → null

zipper:  1 → 5 → 2 → 4 → 3 → null

The Java is those three walks. reverse is the sibling rewire; the zipper saves both successors before it rewires, the same “save next first” order reverse already required.

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

    ListNode second = slow.next;
    slow.next = null;
    second = reverse(second);

    ListNode first = head;
    while (second != null) {
        ListNode firstNext = first.next;
        ListNode secondNext = second.next;
        first.next = second;
        second.next = firstNext;
        first = firstNext;
        second = secondNext;
    }
}

ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Time is O(n) — one walk to the cut, one reverse, one zipper; each node is visited a constant number of times. Space is O(1) besides a handful of pointers. The ArrayList fold is also O(n) time and still pays the extra array.

One node: fast.next is null, the middle loop never runs, second is null, the zipper never runs, you return. Two nodes: no middle step, you cut after L0, reverse a single node, zipper puts L1 back. No special cases.

Cut before you reverse. The even-length cycle is 2.next still pointing into the half you just reversed, so the zipper’s saved successor is a node already in that half. Sorted merge is the wrong combine: comparing val here would scramble the fold the prompt asked for.

What interviewers usually poke next

  • Why not the middle writeup’s loop? That loop returns the second middle. Reverse from there without a predecessor to cut and 2.next still points at 3 while zipper writes 3.next = 2 — a two-node cycle. You can keep a prev behind slow and cut prev.next instead. Say which node you needed before you copy the sibling condition.
  • Palindrome list. Find the middle, reverse the second half, compare the halves. Same first two steps; the third is not a zipper.
  • Recursive fold. Detach the tail on every call and splice it after head. Correct, O(n²) walks, O(n) stack. Say why the three linear passes are the default.
  • Doubly linked. You already have the tail. Walk inward from both ends and rewire. The singly-list bill was that you did not have the tail for free.
  • Restore the original order. Zipper is reversible with the same three ideas in reverse: un-interleave, reverse the back half, splice.
  • Do it by copying values. Correct numbers, wrong identity, extra space. The ArrayList of nodes is the honest brute; a new chain of copied vals is a different list.

You are done with this problem when you can fold 1 → 2 → 3 → 4 on a whiteboard without a cycle, and you can say out loud why this splice is not the sorted merge.