Reorder List

You are given the head of a singly linked list. Reorder the nodes so that the list follows the pattern:

L0 → Ln → L1 → L(n−1) → L2 → L(n−2) → …

You may not modify the values in the nodes — only reorder the nodes themselves.

Examples

• 1 ≤ length of list ≤ 1000
• 1 ≤ Node.val ≤ 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Fundamentals — singly linked list structure and pointer manipulation
• Fast and Slow Pointers — finding the middle of a linked list
• Linked List Reversal — reversing a list in-place with prev and tmp
• Merging Linked Lists — interleaving nodes from two lists into one

1. Brute Force (Array)

Intuition

Store all nodes in an array. Then use two pointers i (front) and j (back) to alternately pick nodes and relink them. Random access to any node becomes O(1), making the reordering straightforward.

Algorithm

• Traverse the list, pushing every node into nodes[].
• Initialize i = 0, j = len - 1.
• While i < j: link nodes[i].next = nodes[j], increment i. If i < j: link nodes[j].next = nodes[i], decrement j.
• Set nodes[i].next = None to terminate.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return

        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next

        i, j = 0, len(nodes) - 1
        while i < j:
            nodes[i].next = nodes[j]
            i += 1
            if i >= j:
                break
            nodes[j].next = nodes[i]
            j -= 1

        nodes[i].next = None

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        List<ListNode> nodes = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) { nodes.add(cur); cur = cur.next; }

        int i = 0, j = nodes.size() - 1;
        while (i < j) {
            nodes.get(i).next = nodes.get(j);
            i++;
            if (i >= j) break;
            nodes.get(j).next = nodes.get(i);
            j--;
        }
        nodes.get(i).next = null;
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — the nodes array.

2. Recursion

Intuition

Use recursion to naturally reach the tail of the list. On the way back up (unwinding), pair the current tail node cur with the front pointer root. Advance root one step forward after each pairing. Stop when the two pointers meet or cross — that is the center of the list.

This avoids an explicit extra array but uses O(n) recursion stack space.

Algorithm

• Define rec(root, cur): recurse to end via cur, return updated root on unwind.
• Base case: if cur is None, return root (the current front pointer).
• Recurse: root = rec(root, cur.next).
• If root is None, or root == cur or root.next == cur: set cur.next = None, return None to stop.
• Otherwise: save tmp = root.next, link root.next = cur, cur.next = tmp, return tmp.

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        def rec(root: ListNode, cur: ListNode) -> ListNode:
            if not cur:
                return root

            root = rec(root, cur.next)
            if not root:
                return None

            tmp = None
            if root == cur or root.next == cur:
                cur.next = None
            else:
                tmp = root.next
                root.next = cur
                cur.next = tmp

            return tmp

        head = rec(head, head.next)

class Solution {
    ListNode root;

    public void reorderList(ListNode head) {
        root = head;
        rec(head.next);
    }

    private ListNode rec(ListNode cur) {
        if (cur == null) return root;
        root = rec(cur.next);
        if (root == null) return null;
        ListNode tmp = null;
        if (root == cur || root.next == cur) {
            cur.next = null;
        } else {
            tmp = root.next;
            root.next = cur;
            cur.next = tmp;
        }
        root = tmp;
        return tmp;
    }
}

Time Complexity: O(n)
Space Complexity: O(n) — recursion call stack.

3. Reverse and Merge (Optimal)

Intuition

Break the problem into three independent steps, each O(n) and O(1) space:

• Find the middle — use slow/fast pointers. When fast reaches the end, slow is at the midpoint.
• Reverse the second half — standard in-place reversal starting from slow.next.
• Merge the two halves — interleave one node from the first half with one from the reversed second half.

After reversing the second half, the two front pointers naturally meet in the middle when interleaving — no special bookkeeping needed.

Common Pitfalls

Incorrectly Finding the Middle Node

Starting fast at head vs head.next produces an off-by-one in the split point. For this problem, start slow = head, fast = head.next. When the loop ends, slow is the last node of the first half — slow.next begins the second half.

# Wrong — fast starts at head, splits off-by-one for even lists:
slow, fast = head, head

# Correct — fast starts one ahead:
slow, fast = head, head.next

Forgetting to Disconnect the Two Halves

After finding the middle, slow.next = None must be set before reversing. Without this, the reversal step creates a cycle (the tail of the reversed second half still points into the first half), causing an infinite loop or a corrupted list during merging.

Losing References During Merge

When relinking nodes during the merge, you overwrite first.next and second.next before saving them. Always save both next pointers first:

# Wrong — overwrites first.next before saving it:
first.next = second
second.next = first.next  # now this is second itself!

# Correct — save both nexts before modifying:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2