Reorder List - Solution & Explanation

Problem Overview: You are given the head of a singly linked list. The goal is to reorder nodes so the list follows the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 .... The structure must be modified in-place without changing node values—only pointers can be rearranged.

Approach 1: Using Array List (O(n) time, O(n) space)

This approach copies all nodes into an array-like structure so you can access both ends easily. First iterate through the linked list and push each node into an ArrayList or dynamic array. Then use two pointers: one starting at the beginning and one at the end. Alternate linking nodes from the front and back while moving the pointers inward. Because random access is O(1), the reordering becomes straightforward. The tradeoff is extra memory proportional to the number of nodes. This approach is simple to reason about and helpful when first understanding pointer rearrangement in a linked list.

Approach 2: Reverse Second Half and Merge (O(n) time, O(1) space)

This is the optimal in-place technique and the one most interviewers expect. First find the middle of the list using the classic slow and fast pointer strategy from two pointers. Once the midpoint is located, reverse the second half of the list. Now you have two lists: the original first half and a reversed second half. Finally merge them by alternating nodes—take one node from the first half, then one from the reversed half, and repeat until the lists are exhausted.

The key insight is that reversing the second half allows you to access the last nodes in forward order without using extra memory. Reversal itself runs in O(n) time and constant space by iteratively updating next pointers. During the merge phase, pointers are carefully rewired so nodes interleave correctly without losing references. This technique relies purely on pointer manipulation and avoids auxiliary structures like a stack or array.

Recommended for interviews: The reverse-and-merge approach is the expected solution because it runs in O(n) time and O(1) extra space. Interviewers often want to see if you can combine multiple linked list techniques: finding the middle, reversing a list, and merging two lists. Starting with the array approach demonstrates the core idea, but implementing the in-place method shows stronger mastery of pointer manipulation.