Reorder List

Reorder List

What is this problem about?

The Reorder List interview question gives you a singly linked list L0 → L1 → ... → Ln-1 → Ln and asks you to reorder it in-place to the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... You must not modify node values — only node pointers. This problem is a synthesis of three fundamental linked list techniques applied in sequence.

Why is this asked in interviews?

This MEDIUM problem is asked at Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe because it tests three linked list building blocks in combination: finding the midpoint (slow/fast pointers), reversing a linked list, and merging two linked lists in an interleaved fashion. Each is a standalone interview question — combining all three demonstrates mastery of linked list manipulation.

Algorithmic pattern used

The pattern is three-phase linked list surgery:

1. Find the middle using slow/fast pointers.
2. Reverse the second half of the list in-place.
3. Merge the first half and the reversed second half by alternating nodes.

This achieves O(n) time and O(1) extra space.

Example explanation

List: 1 → 2 → 3 → 4 → 5

Step 1 — Find middle: slow/fast pointers → middle is node 3. Split into 1 → 2 → 3 and 4 → 5.

Step 2 — Reverse second half: 4 → 5 becomes 5 → 4.

Step 3 — Merge: interleave 1 → 2 → 3 and 5 → 4:

• Take 1 from first, 5 from second: 1 → 5
• Take 2 from first, 4 from second: 1 → 5 → 2 → 4
• Take 3 from first (second is exhausted): 1 → 5 → 2 → 4 → 3

Result: 1 → 5 → 2 → 4 → 3.

Common mistakes candidates make

• Not severing the connection between the first and second halves after finding the midpoint, causing a cycle.
• Reversing the entire list instead of only the second half.
• Losing a node during the merge by overwriting a pointer before saving the next node.
• Getting the midpoint wrong — for an even-length list, the slow pointer should stop at the first of the two middle nodes.

Interview preparation tip

Reorder List is the culmination of three foundational linked list patterns. If you can implement each of the three steps independently (find middle, reverse list, merge two lists), combining them is straightforward. Practice each building block in isolation first. In an interview, verbally walk through the three steps before coding — this signals a structured, top-down approach that interviewers at Apple and Adobe explicitly look for.