Difficulty: MediumLinked List

Reorder List

Problem in Plain English

Given the head of a singly linked list, reorder its nodes in place to alternate from the front and the back (first, last, second, second-last, and so on) without changing any node values.

Problem Statement

Given the head of an acyclic singly linked list, rearrange its nodes in place by taking the first node, the last node, the second node, the second-last node, and continuing inward until every node appears once.

Change only the next links. Do not change values or replace nodes with copies. The head remains the same node, the final tail points to null, and the procedure returns no new list.

Constraints

The number of nodes satisfies $1 \le n \le 50000$ .
Each node value satisfies $1 \le \mathrm{Node.val} \le 1000$ .
The input is an acyclic singly linked list; rearrange the existing nodes and preserve their values.

Examples

Example 1

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Take node 1 from the front and node 4 from the back, then take nodes 2 and 3. All four original nodes remain in the list and node 3 becomes the null-terminated tail.

Example 2

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

The pairs are 1 with 5 and 2 with 4. The middle node 3 has no partner, so it appears once at the tail; the first half must be at least as long as the second.

Example 3

Input: head = [7]
Output: [7]

There is only one original node. It is both head and tail, so its value and null next link stay unchanged.

Example 4

Input: head = [2,2,3,2]
Output: [2,2,2,3]

Repeated values do not identify nodes: the order uses original positions 0, 3, 1, 2. Swapping integer values would not satisfy the required node rearrangement.

Intuition

The target order needs access to both ends, but a singly linked list only walks forward. For Example 1, the front supplies 1 then 2 while the back supplies 4 then 3. An array of node references provides backward access directly; the constant-space alternative splits the list and reverses the back half, making the required back-to-front order available as a forward walk. In either method, save access to the remaining nodes before changing their links.

Approaches

Store Nodes in Array

Solution Details

Reveal Store Nodes in Array: intuition, complexity, and code

Intuition

Store references to the original nodes in an array, then move two indices inward to select the next front and back node. Example 1 selects indices 0, 3, 1, 2. This buys backward access with linear extra space; the references also keep every node reachable even while old links are being overwritten.

Step-by-Step Logic

Walk the original list and collect node references before changing any links. Example 1 gives nodes = [1,2,3,4]; initialize l = 0 and r = 3.
While the indices differ, link the current left node to the current right node, then advance the left index. Initially this writes 1.next = 4 and moves l to 1.
If the indices have met, stop to avoid a self-link. Otherwise connect the right node to the new left node and decrement the right index. Example 1 writes 4.next = 2 and moves r to 2.
Repeat on the unused interval. Linking 2.next = 3 moves l to 2, where it meets r, so the final back-to-front link is skipped.
Set the final node next link to null, even if the loop never ran. Example 1 clears 3.next, leaving [1,4,2,3] in the original nodes.

Why It Works

The array records every input node exactly once before rewiring begins. At each loop entry, indices outside the inclusive interval from l to r have been selected in the required alternating order, while that interval contains precisely the unused nodes. Linking the left endpoint to the right endpoint selects the next pair; incrementing l and decrementing r removes them from the interval. If the indices meet after selecting the back node, that node already closes the final pair, so the loop stops before linking it to itself. Otherwise the back node links to the next left endpoint. Finally clearing nodes[l].next removes any stale forward link. Thus every original node appears once, with unchanged value, in the required order and with no cycle.

Dry Run

Store Nodes in Array: variable states at each step
Action	l	r	Link written	Fixed order selected so far	Unused indices
Collect all references	0	3	none	none	0 through 3
Select front and back	0 -> 1	3	1.next = 4	1,4	1 through 2
Prepare next front	1	3 -> 2	4.next = 2	1,4	1 through 2
Select final pair	1 -> 2	2	2.next = 3	1,4,2,3	none
Indices meet; stop	2	2	skip back-to-front link	1,4,2,3	none
Clear stale tail link	2	2	3.next = null	[1,4,2,3]	none

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

The collection pass visits all n nodes; the two indices then select each node once. The array holds n node references and may have linear spare capacity, so auxiliary space is linear. No replacement ListNode objects or output array are allocated by the procedure.

Code

Solution.java

1import java.util.ArrayList;2import java.util.List;3
4class ListNode {5    int val;6    ListNode next;7    ListNode(int val) { this.val = val; }8}9class Solution {10    public void reorderList(ListNode head) {11        if (head == null) return;12        List<ListNode> nodes = new ArrayList<>();13        for (ListNode curr = head; curr != null; curr = curr.next) nodes.add(curr);14        int l = 0, r = nodes.size() - 1;15        while (l < r) {16            nodes.get(l).next = nodes.get(r);17            l++;18            // When the endpoints meet, another link would point a node at itself.19            if (l == r) break;20            nodes.get(r).next = nodes.get(l);21            r--;22        }23        // The last selected node still carries an old link; remove it to avoid a cycle.24        nodes.get(l).next = null;25    }26}

Hints

Hint 1

A singly linked list cannot step backwards, so the back-half nodes must be reached another way.

Hint 2

Reversing the second half makes its nodes arrive in exactly the order the weave needs.

Hint 3

Split at the slow pointer, reverse the back half, then alternate nodes from the two halves.

Edge Cases

A singleton stays the same node with a null next link; a two-node list already has the target order.
An odd-length list keeps one unpaired center node in the front half, which becomes the final tail.
An even-length list exhausts both halves together; never link the meeting array endpoint to itself.
Repeated values still represent distinct nodes; compare original node positions rather than deduplicating or swapping values.
At 50000 nodes, use iterative walks. The pointer-only solution avoids the linear reference array allocated by the first approach.

Common Mistakes and Interview Tips

Changing values or constructing a replacement list violates the in-place identity requirement even if the printed values match.
Failing to cut slow.next before reversing allows an old link between halves to create a cycle during the merge.
Overwriting either merge successor before saving it can lose the remaining nodes of that half.
Using a different midpoint convention without changing the merge logic may leave the back half longer and dereference a null first pointer.
For the array method, omitting the final null link leaves stale links and often a cycle. Trace odd and even lengths separately in an interview.
Clarify that the procedure returns nothing and keeps the caller head; it mutates the nodes themselves.

Key Takeaway

When both ends of a list are needed at once, split at the middle, reverse the back half, then walk the halves together.