DSA-054 · Split, reverse, and weave disjoint halves

Reorder List

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 5007 deterministic checks. Learner drafts are not executed.

Understand the problem

Reorder N0→N1→…→N(L−1) into N0→N(L−1)→N1→N(L−2)→… by changing next links. Return the original head, or null for an empty list. Do not copy nodes or change values.

Input is null or a finite acyclic chain of at most 100,000 nodes with arbitrary final int values. The caller permits destructive next-link changes and ensures no concurrent traversal relies on the original order.
The output contains every original identity exactly once, in alternating front/back order, and terminates at null. The original head remains the returned head for every nonempty input.
Empty and singleton inputs are unchanged; length two is already in the required order. Equal values do not remove the requirement to reorder identities. Cyclic inputs are outside the contract.

Examples

Input: N0(1)→N1(2)→N2(3)→N3(4)
Output: N0→N3→N1→N2→null
Split after N1, reverse N2→N3 into N3→N2, then weave.
Input: N0→N1→N2→N3→N4
Output: N0→N4→N1→N3→N2→null
The first half has the extra middle node N2, which remains the final node.
Input: N0(5)→N1(5)→N2(5)
Output: N0→N2→N1→null
Checking only values would miss an implementation that never changes the links.

Before you start

Iterative link reversal (DSA-049)
Slow/fast midpoint and node identity

Recognize the structure

The desired order alternates the beginning of one sequence with the reverse of its ending. Midpoint splitting plus reversing one half converts repeated tail retrieval into two forward traversals. Repeatedly scanning for the last node would take quadratic time.

Try before revealing

Hint 1

Can the desired order be written as alternating two simpler lists?

Hint 2

Split after the first-half tail, then reverse the shorter second half.

Hint 3

Save both successors, link first→second→nextFirst, and advance through the saved references.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Collect original references, then alternate indices

Store references in an ArrayList, then link indices left=0,right=L−1 alternately while left<=right. For five nodes, select [0,4,1,3,2], and clear the final tail.next. This is O(L) time and O(L) auxiliary references, preserving node identities. The array supplies backward access that a singly linked list lacks; reversing the second half supplies that access with constant workspace.

Improve the baseline

Choose the first-half tail

Start middle and fast at head; move while fast.next and fast.next.next exist. middle ends at index floor((L−1)/2), so the first half has ceil(L/2) nodes.

Disconnect before reversing

Save second=middle.next, then set middle.next=null. Reverse second iteratively using a saved successor before each edge write. The halves now form disjoint acyclic chains, with the first at least as long as the second.

Weave without losing either frontier

Save nextFirst and nextSecond before changing either edge. Link first→second→nextFirst, then advance to the saved references. Stop when the shorter second chain is exhausted; the remaining first node, if any, is already null-terminated.

Why it is correct

Correct partition

The midpoint guard makes the first half contain ceil(L/2) nodes and the second floor(L/2). The explicit null split removes their only connecting edge, and reversal preserves every second-half identity exactly once.

Weaving invariant

After k iterations the output starts N0,N(L−1),…,N(k−1),N(L−k). first and second root the remaining front-order first half and reverse-order second half. Saving both successors preserves these suffixes; inserting one node from each extends exactly the required alternating sequence.

Termination and coverage

Each iteration consumes one second-half node, so there are floor(L/2) iterations. A first-half node exists whenever a second-half node exists. At exhaustion no node is duplicated or omitted, and the previously split first-half tail supplies the null termination for both parities.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayList;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node next;
        public Node(int value) { this.value = value; }
    }

    public static Node reorder(Node head) {
        if (head == null || head.next == null) return head;
        Node middle = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            middle = middle.next;
            fast = fast.next.next;
        }
        Node second = middle.next;
        middle.next = null;
        Node previous = null;
        while (second != null) {
            Node saved = second.next;
            second.next = previous;
            previous = second;
            second = saved;
        }
        Node first = head;
        second = previous;
        while (second != null) {
            Node nextFirst = first.next;
            Node nextSecond = second.next;
            first.next = second;
            second.next = nextFirst;
            first = nextFirst;
            second = nextSecond;
        }
        return head;
    }

    public static Node baseline(Node head) {
        ArrayList<Node> nodes = new ArrayList<>();
        for (Node p = head; p != null; p = p.next) nodes.add(p);
        Node dummy = new Node(0), tail = dummy;
        int left = 0, right = nodes.size() - 1;
        while (left <= right) {
            tail.next = nodes.get(left++);
            tail = tail.next;
            if (left <= right) {
                tail.next = nodes.get(right--);
                tail = tail.next;
            }
        }
        tail.next = null;
        return dummy.next;
    }
}

Read the meaningful blocks

Midpoint guard

The fast.next.next condition deliberately leaves the extra node in the first half. The initial 0/1 guard protects dereferences.

Split and reverse

middle.next=null must happen before weaving; retaining the original bridge can make a back edge when the halves interleave.

Save both next references

first.next=second overwrites the first suffix edge, and second.next=nextFirst overwrites the second suffix edge. Both original successors must be saved first.

Complexity

Midpoint, reversal, and weaving are sequential O(L) passes, so total time is O(L), not O(L²). The optimized implementation uses O(1) references and allocates no nodes.

The array baseline uses O(L) auxiliary references and a constant sentinel. A repeated tail-search implementation takes Θ(L²) time despite using constant workspace.

Exact-state walkthroughs

Reveal normal and boundary traces

Even split, reverse, and weave

Input: [1,2,3,4] · Outcome / chain identities: ["N0","N3","N1","N2"]

Step 1 of 9: Handle the small-input guard before dereferencing.

The reorder is an identity permutation; empty/singleton inputs need no writes.

Reorder — split, reverse, and weave

Phase: initial. middle: N0 · fast: N0 · first: N0 · second: null · previous: null

N0: 1next → N1middlefastfirst
N1: 2next → N2
N2: 3next → N3
N3: 4next → null

Cards remain in identity order; follow the named links for traversal order. All cards are original nodes. The two halves are disconnected before weaving.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null}]`
pointers	`{"middle":"N0","fast":"N0","first":"N0","second":null,"previous":null}`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node reorder(Node head) {
11         if (head == null || head.next == null) return head;
12         Node middle = head;
13         Node fast = head;
14         while (fast.next != null && fast.next.next != null) {
15             middle = middle.next;
16             fast = fast.next.next;
17         }
18         Node second = middle.next;
19         middle.next = null;
20         Node previous = null;
21         while (second != null) {
22             Node saved = second.next;
23             second.next = previous;
24             previous = second;
25             second = saved;
26         }
27         Node first = head;
28         second = previous;
29         while (second != null) {
30             Node nextFirst = first.next;
31             Node nextSecond = second.next;
32             first.next = second;
33             second.next = nextFirst;
34             first = nextFirst;
35             second = nextSecond;
36         }
37         return head;
38     }
39 
40     public static Node baseline(Node head) {
41         ArrayList<Node> nodes = new ArrayList<>();
42         for (Node p = head; p != null; p = p.next) nodes.add(p);
43         Node dummy = new Node(0), tail = dummy;
44         int left = 0, right = nodes.size() - 1;
45         while (left <= right) {
46             tail.next = nodes.get(left++);
47             tail = tail.next;
48             if (left <= right) {
49                 tail.next = nodes.get(right--);
50                 tail = tail.next;
51             }
52         }
53         tail.next = null;
54         return dummy.next;
55     }
56 }
57

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Handle the small-input guard before dereferencing.
The reorder is an identity permutation; empty/singleton inputs need no writes.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null}]
pointers
{"middle":"N0","fast":"N0","first":"N0","second":null,"previous":null}
phase
"initial"
Find the first-half tail.
The first half will own the extra node for odd lengths.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":null,"previous":null}
phase
"middle"
Disconnect the two halves before reversing.
Both halves are disjoint acyclic chains and the first is at least as long.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null},{"id":"N2","value":3,"next":"N3"},{"id":"N3","value":4,"next":null}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":"N2","previous":null}
phase
"split"
Reverse one original second-half edge, retaining its successor.
previous roots the reversed prefix; second roots the untouched remainder of the second half.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null},{"id":"N2","value":3,"next":null},{"id":"N3","value":4,"next":null}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":"N3","previous":"N2"}
phase
"reverse"
Reverse one original second-half edge, retaining its successor.
previous roots the reversed prefix; second roots the untouched remainder of the second half.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null},{"id":"N2","value":3,"next":null},{"id":"N3","value":4,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":null,"previous":"N3"}
phase
"reverse"
Prepare to weave the two frontiers.
The first frontier runs from the front, the second from the back.
nodes
[{"id":"N0","value":1,"next":"N1"},{"id":"N1","value":2,"next":null},{"id":"N2","value":3,"next":null},{"id":"N3","value":4,"next":"N2"}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":"N3","previous":"N3"}
phase
"ready"
Weave one pair using both saved successors.
The emitted front/back pairs are final and both remaining frontiers stay reachable.
nodes
[{"id":"N0","value":1,"next":"N3"},{"id":"N1","value":2,"next":null},{"id":"N2","value":3,"next":null},{"id":"N3","value":4,"next":"N1"}]
pointers
{"middle":"N1","fast":"N2","first":"N1","second":"N2","previous":"N3"}
phase
"weave"
nextFirst
"N1"
nextSecond
"N2"
Weave one pair using both saved successors.
The emitted front/back pairs are final and both remaining frontiers stay reachable.
nodes
[{"id":"N0","value":1,"next":"N3"},{"id":"N1","value":2,"next":"N2"},{"id":"N2","value":3,"next":null},{"id":"N3","value":4,"next":"N1"}]
pointers
{"middle":"N1","fast":"N2","first":null,"second":null,"previous":"N3"}
phase
"weave"
nextFirst
null
nextSecond
null
Return the documented outcome after all required mutation or restoration.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
["N0","N3","N1","N2"]

Odd length retains the middle node

Input: [5,5,5,5,5] · Outcome / chain identities: ["N0","N4","N1","N3","N2"]

Step 1 of 10: Handle the small-input guard before dereferencing.

The reorder is an identity permutation; empty/singleton inputs need no writes.

Reorder — split, reverse, and weave

Phase: initial. middle: N0 · fast: N0 · first: N0 · second: null · previous: null

N0: 5next → N1middlefastfirst
N1: 5next → N2
N2: 5next → N3
N3: 5next → N4
N4: 5next → null

Cards remain in identity order; follow the named links for traversal order. All cards are original nodes. The two halves are disconnected before weaving.

State after this step
Variable	Value
nodes	`[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N4"},{"id":"N4","value":5,"next":null}]`
pointers	`{"middle":"N0","fast":"N0","first":"N0","second":null,"previous":null}`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node reorder(Node head) {
11         if (head == null || head.next == null) return head;
12         Node middle = head;
13         Node fast = head;
14         while (fast.next != null && fast.next.next != null) {
15             middle = middle.next;
16             fast = fast.next.next;
17         }
18         Node second = middle.next;
19         middle.next = null;
20         Node previous = null;
21         while (second != null) {
22             Node saved = second.next;
23             second.next = previous;
24             previous = second;
25             second = saved;
26         }
27         Node first = head;
28         second = previous;
29         while (second != null) {
30             Node nextFirst = first.next;
31             Node nextSecond = second.next;
32             first.next = second;
33             second.next = nextFirst;
34             first = nextFirst;
35             second = nextSecond;
36         }
37         return head;
38     }
39 
40     public static Node baseline(Node head) {
41         ArrayList<Node> nodes = new ArrayList<>();
42         for (Node p = head; p != null; p = p.next) nodes.add(p);
43         Node dummy = new Node(0), tail = dummy;
44         int left = 0, right = nodes.size() - 1;
45         while (left <= right) {
46             tail.next = nodes.get(left++);
47             tail = tail.next;
48             if (left <= right) {
49                 tail.next = nodes.get(right--);
50                 tail = tail.next;
51             }
52         }
53         tail.next = null;
54         return dummy.next;
55     }
56 }
57

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Handle the small-input guard before dereferencing.
The reorder is an identity permutation; empty/singleton inputs need no writes.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"middle":"N0","fast":"N0","first":"N0","second":null,"previous":null}
phase
"initial"
Find the first-half tail.
The first half will own the extra node for odd lengths.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"middle":"N1","fast":"N2","first":"N0","second":null,"previous":null}
phase
"middle"
Find the first-half tail.
The first half will own the extra node for odd lengths.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":"N3"},{"id":"N3","value":5,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"middle":"N2","fast":"N4","first":"N0","second":null,"previous":null}
phase
"middle"
Disconnect the two halves before reversing.
Both halves are disjoint acyclic chains and the first is at least as long.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":"N4"},{"id":"N4","value":5,"next":null}]
pointers
{"middle":"N2","fast":"N4","first":"N0","second":"N3","previous":null}
phase
"split"
Reverse one original second-half edge, retaining its successor.
previous roots the reversed prefix; second roots the untouched remainder of the second half.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":null},{"id":"N4","value":5,"next":null}]
pointers
{"middle":"N2","fast":"N4","first":"N0","second":"N4","previous":"N3"}
phase
"reverse"
Reverse one original second-half edge, retaining its successor.
previous roots the reversed prefix; second roots the untouched remainder of the second half.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":null},{"id":"N4","value":5,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","first":"N0","second":null,"previous":"N4"}
phase
"reverse"
Prepare to weave the two frontiers.
The first frontier runs from the front, the second from the back.
nodes
[{"id":"N0","value":5,"next":"N1"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":null},{"id":"N4","value":5,"next":"N3"}]
pointers
{"middle":"N2","fast":"N4","first":"N0","second":"N4","previous":"N4"}
phase
"ready"
Weave one pair using both saved successors.
The emitted front/back pairs are final and both remaining frontiers stay reachable.
nodes
[{"id":"N0","value":5,"next":"N4"},{"id":"N1","value":5,"next":"N2"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":null},{"id":"N4","value":5,"next":"N1"}]
pointers
{"middle":"N2","fast":"N4","first":"N1","second":"N3","previous":"N4"}
phase
"weave"
nextFirst
"N1"
nextSecond
"N3"
Weave one pair using both saved successors.
The emitted front/back pairs are final and both remaining frontiers stay reachable.
nodes
[{"id":"N0","value":5,"next":"N4"},{"id":"N1","value":5,"next":"N3"},{"id":"N2","value":5,"next":null},{"id":"N3","value":5,"next":"N2"},{"id":"N4","value":5,"next":"N1"}]
pointers
{"middle":"N2","fast":"N4","first":"N2","second":null,"previous":"N4"}
phase
"weave"
nextFirst
"N2"
nextSecond
null
Return the documented outcome after all required mutation or restoration.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
["N0","N4","N1","N3","N2"]

Empty reorder

Input: [] · Outcome / chain identities: []

Step 1 of 2: Handle the small-input guard before dereferencing.

The reorder is an identity permutation; empty/singleton inputs need no writes.

Reorder — split, reverse, and weave

Phase: initial. middle: null · fast: null · first: null · second: null · previous: null

No nodes at this step.

Cards remain in identity order; follow the named links for traversal order. All cards are original nodes. The two halves are disconnected before weaving.

State after this step
Variable	Value
nodes	`[]`
pointers	`{"middle":null,"fast":null,"first":null,"second":null,"previous":null}`
phase	`"initial"`

See the affected Java block

 1 import java.util.ArrayList;
 2 
 3 public final class Solution {
 4     public static final class Node {
 5         public final int value;
 6         public Node next;
 7         public Node(int value) { this.value = value; }
 8     }
 9 
10     public static Node reorder(Node head) {
11         if (head == null || head.next == null) return head;
12         Node middle = head;
13         Node fast = head;
14         while (fast.next != null && fast.next.next != null) {
15             middle = middle.next;
16             fast = fast.next.next;
17         }
18         Node second = middle.next;
19         middle.next = null;
20         Node previous = null;
21         while (second != null) {
22             Node saved = second.next;
23             second.next = previous;
24             previous = second;
25             second = saved;
26         }
27         Node first = head;
28         second = previous;
29         while (second != null) {
30             Node nextFirst = first.next;
31             Node nextSecond = second.next;
32             first.next = second;
33             second.next = nextFirst;
34             first = nextFirst;
35             second = nextSecond;
36         }
37         return head;
38     }
39 
40     public static Node baseline(Node head) {
41         ArrayList<Node> nodes = new ArrayList<>();
42         for (Node p = head; p != null; p = p.next) nodes.add(p);
43         Node dummy = new Node(0), tail = dummy;
44         int left = 0, right = nodes.size() - 1;
45         while (left <= right) {
46             tail.next = nodes.get(left++);
47             tail = tail.next;
48             if (left <= right) {
49                 tail.next = nodes.get(right--);
50                 tail = tail.next;
51             }
52         }
53         tail.next = null;
54         return dummy.next;
55     }
56 }
57

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Handle the small-input guard before dereferencing.
The reorder is an identity permutation; empty/singleton inputs need no writes.
nodes
[]
pointers
{"middle":null,"fast":null,"first":null,"second":null,"previous":null}
phase
"initial"
Return the documented outcome after all required mutation or restoration.
An array here is an ordered identity view of the Java head-reference result; an error record denotes the declared exception.
result
[]

Test the contract

Input: null
Output: null
No midpoint dereference.
Input: N0→N1
Output: N0→N1
Already ordered.
Input: Four identities
Output: N0,N3,N1,N2
Even split.
Input: Five equal-valued identities
Output: N0,N4,N1,N3,N2
Odd split and identity preservation.

Common mistakes and counterexamples

Never split the halves

Counterexample: For four nodes the original N1→N2 edge can survive alongside N2→N1 and create a cycle.

Disconnect middle.next before reversing and weaving.

Save only the first successor

Counterexample: Rewriting second.next loses the remainder of the reversed half.

Save nextFirst and nextSecond before either write.

Use value equality as the oracle

Counterexample: All-zero input has the same displayed values in every order.

Check the exact index formula: even output position p maps to p/2, odd p to L−1−p/2.

Assume the halves have equal lengths

Counterexample: An odd input has one extra first-half node.

Stop on second==null and leave the first-half remainder in place.

Follow-ups

Undo the reorder.

Separate even and odd output positions into two lists, reverse the odd-position list, and append it to the even-position list. Save successors and terminate each temporary chain before reconnecting.

Use a doubly linked list.

Front and back references can meet inward without reversing a half, but both next and prev fields must be updated. Define whether old tail/head pointers are part of the API and test reciprocal links.

Avoid all temporary mutation.

A read-only input requires a fresh output or a reference array describing the desired sequence. Node reuse and unchanged original next edges cannot both represent a different singly linked order.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 109/20,000 characters

Self-review

I choose a midpoint convention and state which half owns the middle node.I split before reversal and save both suffix references before weaving.I check exact identities, values, and null termination for both parities.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Linked lists: identity, reachability, and update order

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content and implementations authored for AceYourInterviews. Standard problem names do not imply company-frequency or external platform-difficulty claims.