You are given the head of a singly linked list. Your task is to reorder the list into the following pattern:

L0 → L1 → L2 → ... → Ln-1 → Ln

becomes:

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

You must:

• modify the list in-place
• not change node values
• only reorder node links

Example:

Input: 1 → 2 → 3 → 4
Output: 1 → 4 → 2 → 3

Another:

Input: 1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3

---

Problem Understanding

Key observations:

• The first half stays in order
• The second half appears in reverse order
• Nodes alternate between front and back halves
• Linked list structure makes random access difficult
• We cannot use arrays to rebuild (violates in-place requirement)

So we need a linked-list–friendly strategy.

---

Logic Explained in Simple English

To reorder the list, a clean strategy is:

Step 1: Split the list into two halves

• Use slow/fast pointers
• When fast reaches end, slow is at midpoint

Step 2: Reverse the second half of the list

• Standard linked list reversal
• Now we have:
  • first half in original order
  • second half in reversed order

Step 3: Merge the two halves alternately

Take nodes:

from first half, then from second half, repeatedly

Why this works:

• Splitting isolates first and last nodes
• Reversing prepares nodes in correct backward order
• Merging alternates references without extra space

This avoids index access and follows linked list constraints perfectly.

---

Step-by-Step Approach

1. Edge case: if list has 0 or 1 node → return immediately
2. Use slow/fast pointers to find middle
3. Split list into two halves
4. Reverse second half
5. Interleave nodes:
   • first.next = second
   • second.next = first.next (saved)
6. Stop when second half fully merged

---

Java Implementation

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

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

        // Step 2: reverse second half
        ListNode prev = null;
        ListNode curr = slow.next;
        slow.next = null; // split the list

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: merge two halves
        ListNode first = head;
        ListNode second = prev;

        while (second != null) {
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;

            first.next = second;
            second.next = temp1;

            first = temp1;
            second = temp2;
        }
    }
}

---

Dry Run Example

Input list:

1 → 2 → 3 → 4 → 5

Step 1 — Find middle

Slow ends at 3
Split into:

First: 1 → 2 → 3
Second: 4 → 5

Step 2 — Reverse second half

Second becomes:

5 → 4

Step 3 — Merge alternately

Merge sequence:

1 → 5 → 2 → 4 → 3

Final reordered list:

1 → 5 → 2 → 4 → 3

---

Time and Space Complexity

Time Complexity

O(n)

Finding middle: O(n)
Reversing: O(n)
Merging: O(n)

Space Complexity

O(1)

No extra data structures used

---

Common Mistakes and How to Avoid Them

Mistake 1: Reversing the entire list

Only reverse second half, not entire list.

Mistake 2: Not breaking the list into two parts

If you don’t set:

slow.next = null

you get infinite loops.

Mistake 3: Using arrays or extra lists

Violates in-place requirement.

Mistake 4: Off-by-one midpoint handling

Fast/slow approach ensures proper split for even and odd lengths.

Mistake 5: Incorrect merge termination

Stop merging when second half finishes.