Reorder List - Video Solutions

Problem Overview: You are given the head of a singly linked list. The list must be reordered in-place to follow the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 .... Only node links can change; node values cannot be modified. The challenge is restructuring the list efficiently without using excessive extra memory.

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

The simplest way is to copy all nodes into a dynamic array or list. Once stored, you can access nodes from both ends using two pointers: one starting at index 0 and the other at n-1. Reconnect nodes alternately by linking the left pointer node, then the right pointer node, then moving inward. This works because arrays allow constant-time indexing, which makes picking elements from the front and back trivial. The downside is the extra O(n) memory needed to store references to every node.

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, locate the middle of the list using the classic slow/fast pointer technique from two pointers. Once the midpoint is found, split the list into two halves. Reverse the second half using standard linked list reversal.

After reversal, merge the two halves by alternating nodes. Start with the head of the first half and the head of the reversed second half. Attach one node from the first list, then one from the second, and continue until the second half is exhausted. Because the second half was reversed, nodes naturally appear in the required order Ln, Ln-1, .... This approach only modifies pointers and does not allocate extra data structures, which keeps space complexity at O(1).

The key insight is that the required order is essentially an interleaving of the first half and the reversed second half. Breaking the problem into three deterministic steps—find middle, reverse, merge—keeps the logic simple and avoids complicated pointer juggling.

Some implementations also use a stack to access nodes from the end, which conceptually mirrors the array approach but with O(n) auxiliary space. The reverse-and-merge method avoids that overhead.

Recommended for interviews: The reverse second half and merge approach is the expected solution. It demonstrates mastery of linked list manipulation, slow/fast pointers, and in-place reversal. Starting with the array-based idea shows you understand the ordering requirement, but implementing the O(n) time and O(1) space method shows stronger algorithmic skill.