Reorder List

Q: What is the time complexity of Reorder List?

O(n). Each step—finding the middle, reversing the second half, and merging—traverses the list at most once, resulting in linear time complexity.

Q: What pattern does Reorder List use?

The Pattern: Linked List (Fast & Slow Pointers + In-place Reversal + Merge) The Heuristic: When reordering a linked list in a pattern involving nodes from both ends, use fast and slow pointers to find the midpoint, reverse the second half in-place to access nodes from the end efficiently, and then merge the two halves by alternating nodes to achieve the desired order without extra space.

Medium In-place Reversal of a Linked List

Problem

Given the head of a singly linked list, reorder the list to follow the pattern: first node, last node, second node, second last node, and so on, modifying the list in-place without altering node values.

The number of nodes in the list is in the range [1, 5 * 10⁴]
1 ≤ Node.val ≤ 1000

Example

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

Output: [1,4,2,3]

The brute-force approach would be to extract all nodes into an array, then reorder by alternating from the front and back, but this requires O(n) extra space. The optimal approach uses the linked list structure directly: first find the middle of the list, reverse the second half, and then merge the two halves by alternating nodes. This approach achieves O(n) time and O(1) space. For example, starting with [1,2,3,4], the middle is at node 2. The second half [3,4] is reversed to [4,3]. Then merging [1,2] and [4,3] alternately produces [1,4,2,3].

Approach

Straightforward Solution

A naive solution extracts all nodes into an array, then uses two pointers to reorder by alternating from front and back. This uses O(n) extra space and is not optimal.

Core Observation

The problem requires rearranging nodes in a specific interleaved order without extra space. The key insight is that the list can be split into two halves, the second half reversed, and then merged alternately to achieve the desired order.

Path to Optimal

Preview

The optimal approach uses the fast and slow pointer technique to find the middle of the list in O(n) time. Then, the second half of the list is reversed in-place…

Full step-by-step walkthrough on Pro →

Optimal Approach

Use two pointers to find the middle node, split the list into two halves, reverse the second half in-place, and then merge the two halves by alternating nodes. This achieves the required reordering in O(n) time and O(1) space.

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each step—finding the middle, reversing the second half, and merging—traverses the list at most once, resulting in linear time complexity.

Space

O(1)

All operations are done in-place without allocating extra data structures proportional to the input size, using only a fixed number of pointers.

Pattern Spotlight

Linked List (Fast & Slow Pointers + In-place Reversal + Merge)

When reordering a linked list in a pattern involving nodes from both ends, use fast and slow pointers to find the midpoint, reverse the second half in-place to access nodes from the end efficiently, and then merge the two halves by alternating nodes to achieve the desired order without extra space.

Solution

Python

1class Solution:
  def reorderList(self, head: ListNode) -> None:
      slow, fast = head, head.next
      while fast and fast.next:
          slow = slow.next
          fast = fast.next.next
      
      second = slow.next
      prev = None
      slow.next = None
      while second:
          tmp = second.next
          second.next = prev
          prev = second
          second = tmp
      
      first, second = head, prev
      while second:
          tmp1, tmp2 = first.next, second.next
          first.next = second
          second.next = tmp1
          first, second = tmp1, tmp2

Step-by-Step Solution

Locate the Middle Node Using Fast and Slow Pointers

3slow, fast = head, head.next
4while fast and fast.next:
5    slow = slow.next
6    fast = fast.next.next

Objective

To find the midpoint of the linked list efficiently in a single pass.

Key Insight

Using two pointers moving at different speeds (fast moves two steps, slow moves one) allows locating the middle node when fast reaches the end. This technique splits the list into two halves without extra space or multiple passes.

Interview Quick-Check

Core Logic

Fast and slow pointers traverse the list simultaneously; when fast reaches the end, slow is at the midpoint, enabling O(n) time middle detection.

State & Boundaries

The loop condition `while fast and fast.next` ensures the slow pointer stops at the node before the start of the second half.

Common Pitfalls & Bugs

Initializing fast to `head.next` instead of `head` ensures correct middle for even-length lists, preventing off-by-one errors.

Reverse the Second Half of the List In-Place

To reverse the nodes after the midpoint to enable efficient merging from the end.

Merge the Two Halves by Alternating Nodes

To interleave nodes from the first half and the reversed second half to achieve the final reordered list.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 13 Critical

second.next = prev

Reverse the current node's next pointer to point to prev.

This is the core reversal step that flips the direction of the linked list pointers.

Line 12 Critical

tmp = second.next

Store next node temporarily before changing pointers.

Preserving the next node is essential to continue traversal after pointer reversal.

Line 19 Critical

tmp1, tmp2 = first.next, second.next

Store next nodes of first and second pointers before re-linking.

Preserving next nodes prevents losing access to the remaining list during pointer reassignment.

Full line-by-line criticality + rationale for all 18 lines available on Pro.

Test Your Understanding

Why is reversing the second half of the list necessary before merging?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Reorder List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Reorder List drill

or drill a free problem

1	`class Solution:`
2	`def reorderList(self, head: ListNode) -> None:`
3	`slow, fast = head, head.next`
4	`while fast and fast.next:`
5	`slow = slow.next`
6	`fast = fast.next.next`
7
8	`second = slow.next`
9	`prev = None`
10	`slow.next = None`
11	`while second:`
12	`tmp = second.next`
13	`second.next = prev`
14	`prev = second`
15	`second = tmp`
16
17	`first, second = head, prev`
18	`while second:`
19	`tmp1, tmp2 = first.next, second.next`
20	`first.next = second`
21	`second.next = tmp1`
22	`first, second = tmp1, tmp2`

3	`slow, fast = head, head.next`
4	`while fast and fast.next:`
5	`slow = slow.next`
6	`fast = fast.next.next`