AlgoInsight

Q&A

How to reorder a linked list in-place

By AlgoInsight Team2026-06-07data-structures

Overview

"Reorder in-place" means rearranging the existing nodes (changing next pointers) without allocating a new list, ideally in O(1) extra space. The signature problem (LeetCode 143) weaves the list from the front and back alternately. The elegant solution composes three standard linked-list techniques.

graph TD
    A["L0→L1→L2→L3→L4→L5"] --> B[1. Find middle: slow/fast pointers]
    B --> C[2. Reverse second half: L5→L4→L3]
    C --> D[3. Merge alternately:<br/>L0→L5→L1→L4→L2→L3]
    style D fill:#1e1b4b,color:#fff

The Three-Step Algorithm

Step 1: Find the middle (slow/fast pointers)

Advance slow by one and fast by two; when fast reaches the end, slow is at the middle.

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow = end of the first half

Step 2: Reverse the second half

Reverse the portion after slow using the standard iterative reversal.

ListNode second = slow.next;
slow.next = null;                 // split the list into two halves
ListNode prev = null;
while (second != null) {
    ListNode next = second.next;
    second.next = prev;           // reverse the link
    prev = second;
    second = next;
}
// prev = head of the reversed second half

Step 3: Merge the two halves alternately

Weave nodes from the first half and the reversed second half.

ListNode first = head, secondHalf = prev;
while (secondHalf != null) {
    ListNode t1 = first.next, t2 = secondHalf.next;
    first.next = secondHalf;       // first → secondHalf
    secondHalf.next = t1;          // secondHalf → next first
    first = t1;
    secondHalf = t2;
}

Complete Solution (Java)

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    // 1. middle
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }

    // 2. reverse second half
    ListNode second = slow.next, prev = null;
    slow.next = null;
    while (second != null) {
        ListNode next = second.next;
        second.next = prev; prev = second; second = next;
    }

    // 3. merge alternately
    ListNode first = head;
    while (prev != null) {
        ListNode t1 = first.next, t2 = prev.next;
        first.next = prev; prev.next = t1;
        first = t1; prev = t2;
    }
}

Trace

Input:  1 → 2 → 3 → 4 → 5
Middle: slow at 3;  first half 1→2→3, second half 4→5
Reverse second: 5→4
Merge:  1→5→2→4→3

Complexity

Why Not Use an Array?

You could copy nodes into an array and reorder by index (O(n) time) - but that uses O(n) extra space. The three-step pointer approach achieves O(1) space, which is what "in-place" demands and what interviewers look for.

Why This Matters in Interviews

This is a popular linked-list problem because it composes three fundamental techniques: slow/fast pointers (find middle), in-place reversal, and two-list merge. Recognizing that the target pattern decomposes into these steps - and achieving O(n)/O(1) - is the signal. Edge cases (empty list, single/two nodes) and correctly splitting at the middle (slow.next = null) are where candidates stumble. Mentioning the array alternative and why it's worse on space shows good trade-off awareness.

Common Pitfalls

References

More answers