Reorder List

mediumLinked List38 stepsJava · Python · C++

Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → …, in place. Find the middle, reverse the second half, then weave the two halves together one node at a time.

▶ Watch the animated trace

Traced input: head = [1, 2, 3, 4, 5] → [1, 5, 2, 4, 3]. Original problem: neetcode.io/problems/reorder-linked-list

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Three linear passes, no extra list.

Key idea

The pattern alternates from the front and the back, so reverse the back half to walk it forward.
Fast/slow pointers find the middle; cut the list there.
Weave: take one from the first half, one from the reversed second half.

Common mistakes

Forgetting to cut the first half (slow.next = null) creates a cycle.
Copying nodes into an array works but uses O(n) space.

Solution

Java

void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode second = slow.next, prev = null;
    slow.next = null;
    while (second != null) {
        ListNode next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }
    ListNode first = head;
    second = prev;
    while (second != null) {
        ListNode n1 = first.next, n2 = second.next;
        first.next = second;
        second.next = n1;
        first = n1;
        second = n2;
    }
}

Python

def reorderList(head: Optional[ListNode]) -> None:
    if not head or not head.next:
        return
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    second, prev = slow.next, None
    slow.next = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    first, second = head, prev
    while second:
        n1, n2 = first.next, second.next
        first.next = second
        second.next = n1
        first, second = n1, n2

C++

void reorderList(ListNode* head) {
    if (!head || !head->next) {
        return;
    }
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *second = slow->next, *prev = nullptr;
    slow->next = nullptr;
    while (second) {
        ListNode* next = second->next;
        second->next = prev;
        prev = second;
        second = next;
    }
    ListNode* first = head;
    second = prev;
    while (second) {
        ListNode *n1 = first->next, *n2 = second->next;
        first->next = second;
        second->next = n1;
        first = n1;
        second = n2;
    }
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Even length Halves [1, 2] and [4, 3] weave together.	`head = [1, 2, 3, 4]`	`[1, 4, 2, 3]`
Single node Nothing to move.	`head = [1]`	`[1]`
Two nodes Already in order.	`head = [1, 2]`	`[1, 2]`