Reorder List

Difficulty: Medium
Topics: Linked List, Two Pointers, Stack, Recursion
Link: https://leetcode.com/problems/reorder-list/

Problem Description

You are given the head of a singly linked-list. The list can be represented as:


L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:


L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:


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

Example 2:


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

Constraints:

The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000

Solution

1. Problem Deconstruction

Technical Version

Given the head node of a singly linked list, restructure the node linkages to interleave elements from the first half with elements from the reversed second half. Specifically:

Let the original list be $N_0 \rightarrow N_1 \rightarrow \cdots \rightarrow N_{k}$ where $k = n-1$ and $n$ is the node count.
The reordered list must be $N_0 \rightarrow N_k \rightarrow N_1 \rightarrow N_{k-1} \rightarrow N_2 \rightarrow N_{k-2} \rightarrow \cdots$ .
Modifications are restricted to node pointers (.next); node values are immutable.

Beginner Version

Imagine a line of people:

Person 1 stands behind Person 0, Person 2 behind Person 1, and so on.
Rearrange the line so:
- The first person remains first.
- The last person moves to second position.
- The second person moves to third.
- The second-to-last moves to fourth, etc.
You can only change “who stands behind whom,” not swap people.

Mathematical Version

Given a sequence $S = [N_0, N_1, \dots, N_{n-1}]$ , produce a permutation $P$ where:

P = \left(N_0, N_{n-1}, N_1, N_{n-2}, \dots, N_{\left\lfloor \frac{n}{2} \right\rfloor}\right)

such that $\forall i \in [0, n-2], P[i].next = P[i+1]$ , and $P[n-1].next = \text{null}$ .

Constraint Analysis

Node count in $[1, 5 \times 10^4]$ :
- Limitation: Rules out $O(n^2)$ algorithms (e.g., brute force would be $2.5 \times 10^9$ operations).
- Edge Case: Single-node lists require no processing.
Node values $\in [1, 1000]$ :
- Limitation: Values are non-negative, so no special handling for negatives.
- Edge Case: All values identical; algorithm must rely on structure, not values.
Implicit Edge Cases:
- Odd-Length Lists: Middle node becomes the last node (e.g., [1,2,3] → [1,3,2]).
- Even-Length Lists: No leftover nodes (e.g., [1,2,3,4] → [1,4,2,3]).
- List Breakage: Incorrect pointer management can create cycles or breaks.

2. Intuition Scaffolding

Analogies

Real-World Metaphor:
- Deck of Cards: Split a deck, reverse the bottom half, then interleave cards from both halves.
Gaming Analogy:
- RPG Inventory: Merge two item rows—one original, one reversed—by alternating picks.
Math Analogy:
- Vector Transformation: Given vector $\mathbf{v}$ , compute $\mathbf{w}$ where $w_{2i} = v_i$ and $w_{2i+1} = v_{n-1-i}$ for $i \in [0, \lfloor n/2 \rfloor)$ .

Common Pitfalls

Modifying Values: Storing values to rebuild the list violates constraints.
Cycle Creation: Failing to break links when merging (e.g., [1,2,3] cycles if 3.next isn’t set to null).
Incorrect Middle Split: Splitting at wrong node (e.g., first vs second middle in even-length lists).
Stack Overuse: Using $O(n)$ space when $O(1)$ is possible.
Partial Reversal: Only reversing values or nodes without updating pointers.

3. Approach Encyclopedia

Approach 1: Stack-Based ( $O(n)$ Space)

Pseudocode:

def reorderList(head):  
    if not head: return  
    stack = []  
    curr = head  
    # Push all nodes to stack  
    while curr:  
        stack.append(curr)  
        curr = curr.next  
    # Reorder  
    curr = head  
    for _ in range(len(stack) // 2):  
        top = stack.pop()  
        next_node = curr.next  
        curr.next = top  
        top.next = next_node  
        curr = next_node  
    curr.next = None  # Break cycle

Complexity Proof:

Time: $T(n) = n$ (traversal) $+ n/2$ (reordering) $\in O(n)$ .
Space: $S(n) = n$ (stack) $\in O(n)$ .

Visualization:

Original: 1 → 2 → 3 → 4  
Stack: [1,2,3,4]  
Step 1: curr=1, top=4 → 1→4→2  
Step 2: curr=2, top=3 → 2→3→? → 1→4→2→3  
Final: Set 3.next=None → 1→4→2→3

Approach 2: In-Place Reversal ( $O(1)$ Space)

Pseudocode:

def reorderList(head):  
    if not head or not head.next: return  
    # Find middle  
    slow = fast = head  
    while fast and fast.next:  
        slow = slow.next  
        fast = fast.next.next  
    # Split and reverse second half  
    second = slow.next  
    slow.next = None  # Break list  
    prev = None  
    while second:  
        next_node = second.next  
        second.next = prev  
        prev = second  
        second = next_node  
    # Merge  
    first, second = head, prev  
    while second:  
        tmp1, tmp2 = first.next, second.next  
        first.next = second  
        second.next = tmp1  
        first, second = tmp1, tmp2

Complexity Proof:

Time: $T(n) = n/2$ (find middle) $+ n/2$ (reverse) $+ n/2$ (merge) $\in O(n)$ .
Space: $S(n) = 6$ pointers $\in O(1)$ .

Visualization:

Original: 1 → 2 → 3 → 4 → 5  
Step 1 (Split):  
  First half: 1→2→3  
  Second half: 4→5  
Step 2 (Reverse): 5→4  
Step 3 (Merge):  
  1→5→2→4→3

4. Code Deep Dive

Line-by-Line Analysis

class Solution:  
    def reorderList(self, head: Optional[ListNode]) -> None:  
        # Edge: 0 or 1 node  
        if not head or not head.next:  # O(1)  
            return

What: Handle trivial cases.
Why: No processing needed for minimal lists.
How: Check head and head.next.

        # Find middle (slow stops at mid or first mid)  
        slow = fast = head  # O(1)  
        while fast and fast.next:  # O(n/2)  
            slow = slow.next  # Move 1 step  
            fast = fast.next.next  # Move 2 steps

What: Locate split point via Floyd’s cycle-finding.
Why: Split list into two equal halves.
How: fast advances twice as fast; when fast ends, slow is at middle.

        # Split and reverse second half  
        second = slow.next  # Start of second half  
        slow.next = None  # Break first half  
        prev = None  # Reversal pointer  
        while second:  # O(n/2)  
            next_node = second.next  # Save next  
            second.next = prev  # Reverse link  
            prev = second  # Advance prev  
            second = next_node  # Advance second

What: Reverse second half iteratively.
Why: To interleave with first half.
How: Standard reversal; prev becomes head of reversed list.

        # Merge halves  
        first, second = head, prev  # O(1)  
        while second:  # O(n/2)  
            tmp1, tmp2 = first.next, second.next  # Save next pointers  
            first.next = second  # Link first to second  
            second.next = tmp1  # Link second to next first  
            first, second = tmp1, tmp2  # Advance

What: Interleave nodes.
Why: Achieve $N_0 \rightarrow N_k \rightarrow N_1 \cdots$ pattern.
How: Traverse both lists, updating .next pointers alternately.

Edge Case Handling

Example 1 ([1,2,3,4]):
- Split: first=1→2, second=3→4 → reversed second=4→3.
- Merge: 1→4→2→3.
Example 2 ([1,2,3,4,5]):
- Split: first=1→2→3, second=4→5 → reversed second=5→4.
- Merge: 1→5→2→4→3.
Two Nodes ([1,2]):
- After split: first=1, second=2 → reversed second=2.
- Merge: 1→2 (unchanged).

5. Complexity War Room

Hardware-Aware Analysis

Memory: $O(1)$ space uses $\approx 48$ bytes (6 pointers). For $5e4$ nodes, the list consumes $\approx 1.2$ MB (Python node $\approx 24$ bytes), fitting in L2/L3 cache.
Time: $O(n)$ runtime is optimal; $5e4$ operations are trivial (sub-millisecond in C++, $\sim 10$ ms in Python).

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	$O(n^2)$	$O(1)$	9/10	❌ Fails $n=5e4$
Stack-Based	$O(n)$	$O(n)$	8/10	✅ Acceptable
In-Place Rev.	$O(n)$	$O(1)$	7/10	✅ Optimal

6. Pro Mode Extras

Variants

Doubly Linked List:

Approach: Use head/tail pointers and merge inward.

Code Snippet:

left, right = head, tail  
while left != right and left.prev != right:  
    next_left = left.next  
    next_right = right.prev  
    left.next = right  
    right.prev = left  
    right.next = next_left  
    next_left.prev = right  
    left, right = next_left, next_right

Grouped Reordering ( $k$ -Groups):
- Challenge: Reorder blocks of $k$ nodes (e.g., $k=3$ : [1,2,3,4,5,6] → [3,2,1,6,5,4]).
- Solution: Recursive reversal + merging.

Interview Cheat Sheet

Key Insight: Splitting + reversal + merging covers 90% of linked list problems.
Must-Mention:

“This runs in $O(n)$ time and $O(1)$ space by leveraging Floyd’s cycle detection, in-place reversal, and pointer arithmetic.”
Testing Protocol:
1. Empty list.
2. Single node.
3. Odd/even lengths.
4. All values identical.

#143 - Reorder List