Reorder List (LC 143)

Pattern: Linked List — find middle + reverse + merge
Difficulty: Medium
Key Concept: Split the list in half, reverse the second half, then zip-merge first and second halves alternately.

Problem Statement

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

You must not modify the values—only change nodes’ pointers. Do it in O(1) extra memory (i.e., in-place pointer changes).

Input: head.
Output: void (reorder in place); return nothing.

Example: 1 -> 2 -> 3 -> 4 → 1 -> 4 -> 2 -> 3.

---

1. Algorithm & Pseudocode

Brute force

1. Copy all nodes into ArrayList<ListNode>, rebuild order using indices 0, n-1, 1, n-2, ….
2. Space O(n) for the list—violates strict O(1) extra if interviewer counts auxiliary storage.

Pseudocode:

nodes = collect all
i = 0, j = n-1
while i <= j:
    link nodes[i] to nodes[j], alternate

Optimal

1. Middle: slow/fast pointers; split after slow (for even length, first half shorter or per convention).
2. Reverse second half starting from slow.next; break link to get two lists.
3. Merge: p = head, q = head of reversed part; repeatedly p.next swap wiring, advance.

Pseudocode:

mid = findMiddle(head)
second = reverse(mid.next)
mid.next = null
merge(head, second)

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why reverse second half: The pattern pairs front with back; reversed second half lets you consume from the front of both pieces.

Why split at middle: You need two independent chains to merge without revisiting nodes.

Even vs odd length: For odd count, middle node stays in first part; second part is one shorter—merge still works.

---

3. The Dry Run

1 -> 2 -> 3 -> 4

phase	result
find mid	slow ends at 2; split: first 1->2, second 3->4
reverse second	4 -> 3
merge	attach 1->4, 4->2, 2->3, 3->null

Zip steps:

step	first head	second head	action
1	1	4	1.next=4
2	2	3	4.next=2
3	3	null	2.next=3

---

4. Java Solution

Brute Force

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

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) {
            nodes.add(p);
        }
        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: O(n). Space: O(n).

Optimal

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

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

        ListNode second = reverse(slow.next);
        slow.next = null;

        ListNode first = head;
        while (second != null) {
            ListNode t1 = first.next;
            ListNode t2 = second.next;
            first.next = second;
            second.next = t1;
            first = t1;
            second = t2;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• No dummy required for merge if you save t1, t2 next pointers before rewiring—avoids losing links.
• void method mutates list in place; return type matches LeetCode.
• Palindrome list (LC 234) reuses middle + reverse pattern.

---

6. Complexity Summary

Approach	Time	Space	Notes
ArrayList index merge	O(n)	O(n)	Not O(1) extra
Mid + reverse + merge	O(n)	O(1)	Interview standard

---

ASCII — phases

Start:

head
  |
  v
+---+    +---+    +---+    +---+
| 1 |--> | 2 |--> | 3 |--> | 4 |--> null
+---+    +---+    +---+    +---+

After find middle & cut (slow at 2):

first half:          second half:
+---+    +---+       +---+    +---+
| 1 |--> | 2 |       | 3 |--> | 4 |--> null
+---+    +---+       +---+    +---+
              ^slow.next = null (split)

After reverse second half:

first: 1 --> 2 --> null

second (new head at 4):
+---+    +---+
| 4 |--> | 3 |--> null
+---+    +---+

Merge (zip):

1 -----> 4
 ^         \
  \         v
   `-----> 2 -----> 3 --> null

Final:

+---+    +---+    +---+    +---+
| 1 |--> | 4 |--> | 2 |--> | 3 |--> null
+---+    +---+    +---+    +---+