You’ll solve Reorder List by doing three linked-list moves in order: find the middle, reverse the second half, then merge the two halves by alternating nodes. This keeps the solution $O(n)$ time and $O(1)$ extra space.

Problem Statement

Given the head of a singly linked list, reorder the list so that the nodes are arranged in the following order: first node, last node, second node, second last node, and so on. The reordering must be done in-place without modifying the values of the nodes.

Example:

• Input: [1,2,3,4,5]
• Output: [1,5,2,4,3]

Constraints:

• The number of nodes is in the range [1, 5 * 10^4]
• 1 <= Node.val <= 1000

LeetCode Problem Link

How the Algorithm Works

💡 One Sentence Rule (Key Insight)

Split list into two halves, reverse the second half, then merge alternately to achieve the interleaved reordering pattern.

This rule captures the ESSENCE of the algorithm. Every step we take follows from this three-phase approach.

Algorithm Overview

The Reorder List algorithm uses a three-step process that leverages fundamental linked list manipulation techniques. Instead of using extra space to store nodes, we restructure the list connections in-place by applying the classic "find middle, reverse, merge" pattern.

Step-by-Step Process

When we need to reorder a list with an interleaved pattern:

1. Find the middle using fast/slow pointers ← Split the list into equal halves
2. Reverse the second half in-place ← Enable access to "end" nodes efficiently
3. Merge alternately from both halves ← Create the final interleaved pattern
4. Result: Original first-last-second-second-last pattern achieved

Key insight: Reversing the second half transforms end-access from O(n) per node to O(1), making the alternating merge feasible in linear time.

Input

head = [1,2,3,4,5]

Output

[1,5,2,4,3]

Solution

def reorder_list(head: ListNode) -> None:
    """Reorder list by splitting, reversing second half, and merging alternately."""
    # Step 1: Find middle using fast/slow pointers
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Step 2: Reverse second half in-place
    second = slow.next
    prev = None
    slow.next = None  # Break connection
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp
    
    # Step 3: Merge alternately
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Applying the One Sentence Rule

One-sentence-rule framing:

Use linked list manipulation whenever you need to restructure connections between nodes by tracking and updating pointers.

For this problem:

• What connections need restructuring? The linear sequence needs to become an interleaved pattern
• What pointers do we track? Fast/slow for middle detection, prev/curr/next for reversal, first/second for merging
• Why three phases? Each phase sets up the next: split enables independent processing, reversal enables efficient end-access, merge creates final structure

Applying the rule:

The three-phase approach works because each phase uses targeted pointer manipulation:

1. Split phase: Fast/slow pointers detect the midpoint without extra space
2. Reverse phase: Standard three-pointer reversal gives us efficient access to original "end" nodes
3. Merge phase: Alternating pointer reassignment creates the interleaved pattern

Example walkthrough for [1,2,3,4,5]:

1. Split: [1,2,3] + [4,5] → Two independent halves

2. Reverse second: [1,2,3] + [5,4] → Second half now starts from original end

3. Merge alternately:

   • Take 1 from first: [1]
   • Take 5 from second: [1,5]
   • Take 2 from first: [1,5,2]
   • Take 4 from second: [1,5,2,4]
   • Take 3 from first: [1,5,2,4,3] ✓

The pattern emerges because reversing the second half transforms a linear merge into the exact interleaved order we need, using only pointer reassignments without extra space.

Time/Space Complexity

Time: O(n) - Three linear passes through the list (find middle, reverse, merge) Space: O(1) - Only uses a constant number of pointer variables

Key Insights

1. Why reverse the second half? Without reversal, accessing the "last" nodes would require O(n) traversal for each merge step, making the algorithm O(n²)

2. Why fast = head.next? This ensures correct splitting for even-length lists, preventing the second half from being longer than the first

3. Why break the connection? Setting slow.next = None prevents cycles during reversal and ensures two independent lists for clean merging