37.Reorder List

MediumBlind 75Linked List · 3/11

Problem

You are given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln. Reorder it in place to:

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

That is, alternate between taking a node from the front and a node from the back. You may not change node values — only the next pointers. The function returns nothing.

Examples

Input:  head = [1, 2, 3, 4]
Output: [1, 4, 2, 3]
Explanation: front 1, back 4, front 2, back 3.

Input:  head = [1, 2, 3, 4, 5]
Output: [1, 5, 2, 4, 3]
Explanation: front 1, back 5, front 2, back 4, then the middle node 3.

Constraints

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

💡 Key Insight

The answer interleaves the first half with the second half reversed. A singly linked list cannot walk backwards, but we can make the back half walkable from the end by reversing it. So: find the middle (slow/fast pointers), reverse the second half, then merge the two halves alternately — three classic O(n), O(1)-space linked-list moves.

Brute Force (Repeatedly Find the Tail)

TimeO(n²)SpaceO(1)

Intuition

Do exactly what the problem says: at the current node, walk to the end of the list, detach the last node and insert it right after the current node. Then jump two nodes ahead and repeat.

Algorithm

curr = head.
While curr and curr.next and curr.next.next exist:
- Walk to find the second-to-last node prev and the last node last.
- Detach: prev.next = null.
- Insert: last.next = curr.next, curr.next = last.
- curr = last.next (skip over the inserted node).

Visualization

1 -> 2 -> 3 -> 4 -> 5
curr=1: move 5 after 1 -> 1 -> 5 -> 2 -> 3 -> 4
curr=2: move 4 after 2 -> 1 -> 5 -> 2 -> 4 -> 3
curr=3: 3.next is null -> stop

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode curr = head;
        while (curr != null && curr.next != null && curr.next.next != null) {
            // Find the second-to-last node
            ListNode prev = curr;
            while (prev.next.next != null) {
                prev = prev.next;
            }
            ListNode last = prev.next;
            prev.next = null;       // detach the tail
            last.next = curr.next;  // insert it after curr
            curr.next = last;
            curr = last.next;       // move to the next front node
        }
    }
}

Complexity

Time: O(n²) — each of ~n/2 iterations walks to the tail.
Space: O(1) — pointer manipulation only.

Array of Nodes + Two Pointers

TimeO(n)SpaceO(n)

Intuition

The problem is hard only because we cannot index into a linked list. Copy the node references into an ArrayList, then use two indices i (front) and j (back) moving toward each other to relink.

Algorithm

Store all nodes in nodes.
i = 0, j = n - 1.
While i < j:
- nodes[i].next = nodes[j], then i++.
- If i == j, break.
- nodes[j].next = nodes[i], then j--.
nodes[i].next = null to terminate the list.

Visualization

nodes: [1, 2, 3, 4, 5]
        i           j   1 -> 5
           i        j   5 -> 2
           i     j      2 -> 4
              i  j      4 -> 3
              ij        stop; 3.next = null
result: 1 -> 5 -> 2 -> 4 -> 3

Code

java

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            nodes.add(n);
        }
        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j); // front -> back
            i++;
            if (i == j) break;
            nodes.get(j).next = nodes.get(i); // back -> next front
            j--;
        }
        nodes.get(i).next = null; // the middle node becomes the tail
    }
}

Complexity

Time: O(n) — one pass to collect, one pass to relink.
Space: O(n) — the array of node references.

Find Middle + Reverse + MergeOptimal

TimeO(n)SpaceO(1)

Intuition

Split the list into a first half and a second half. Reverse the second half so its last node comes first. Now the answer is just the two halves zipped together: one from the first, one from the second, and so on.

Algorithm

Find the middle with slow and fast pointers (fast moves 2 steps). When fast stops, slow is at the end of the first half.
Split: second = slow.next, then slow.next = null.
Reverse second iteratively.
Merge: with first = head, while second != null, save both next pointers, set first.next = second, second.next = firstNext, then advance both.

Dry Run

flowchart TD
    A["1 -> 2 -> 3 -> 4 -> 5"] -->|"slow/fast: slow stops at 3"| B["first: 1 -> 2 -> 3<br/>second: 4 -> 5"]
    B -->|"reverse second"| C["first: 1 -> 2 -> 3<br/>second: 5 -> 4"]
    C -->|"zip 1 with 5"| D["1 -> 5 -> 2 -> 3<br/>left: 4"]
    D -->|"zip 2 with 4"| E["1 -> 5 -> 2 -> 4 -> 3"]

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        // 1. Find the end of the first half
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. Split and reverse the second half
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }
        second = prev; // head of the reversed second half

        // 3. Merge the two halves alternately
        ListNode first = head;
        while (second != null) {
            ListNode firstNext = first.next;
            ListNode secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

Complexity

Time: O(n) — finding the middle, reversing, and merging are each a linear pass.
Space: O(1) — all work is done by rewiring pointers.

Complexity Comparison

Approach	Time	Space
Repeatedly Find the Tail	O(n²)	O(1)
Array + Two Pointers	O(n)	O(n)
Middle + Reverse + Merge	O(n)	O(1)

Common Pitfalls

Forgetting slow.next = null when splitting — the first half still points into the second half, creating a cycle after the merge.
Starting fast at head instead of head.next changes where slow stops; that still works only if you split consistently, so trace a 2-node and 3-node list.
In the array version, not setting the final node's next to null, leaving a cycle.
Merging with while (first != null) instead of while (second != null) — the first half can be one node longer, so loop on the shorter half.
Creating new nodes or swapping values — the problem requires rewiring the existing nodes.