How do you solve Reorder List in O(1) space?

Find the middle with slow and fast pointers, cut the list after slow, reverse the second half, then take nodes alternately from the first half and the reversed second half.

Where is the list split for even and odd lengths?

The second half starts at slow.next. For 1→2→3→4 slow stops at 3, giving 1→2→3 and 4; for 1→2→3→4→5 it gives 1→2→3 and 4→5.

What is the time complexity of Reorder List?

O(n): finding the middle, reversing and merging each take one pass, and no extra list or deque is created.

Reorder List

Reorder a linked list in a specific pattern.

MediumSolve on LeetCode

Problem Understanding

Take a singly linked list L0 → L1 → … → Ln - 1 → Ln and rearrange its nodes so they alternate between the front and the back, changing only the links and never the values:

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

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

Attempt 1: Array/Deque (Brute Force)

We can put all nodes into a Deque (Double Ended Queue). Then, we can pop from the front and back alternately to build the new list.

Drawback: Uses O(N) extra space to store all node references.

Visualizing the Issue

We need access to the end of the list, but we only have a forward pointer. Does this remind you of Palindrome check? We needed to access the end there too.

The Intuition: Split, Reverse, Merge

Find Middle: Split the list into two halves.
Reverse Second Half: The second half starts at slow.next. For 1->2->3->4, slow stops at 3, so the halves are 1->2->3 and 4; for 1->2->3->4->5 they are 1->2->3 and 4->5, reversed to 5->4.
Merge: Pick one from first, then one from second. 1 -> 4 -> 2 -> 3.

Interactive Walkthrough

5 NODES · L0 → Ln → L1 → …

START AT HEAD

slow fast

→

→ NULL

Phase

middle

slow and fast start at head, 1

slow moves to 2; fast moves two to 3

Values

Legend & Complexity

slow, curr or first: the pointer driving this phase

fast, prev or second

The second half, once cut off

The reordered list

→ n: a link into the other row

Time

O(n)

Space

O(1)

Watch the three steps as structure: the cut at slow.next = NULL turns one row into two, flipping the second half makes that row read backward, and each splice links a node from the lower row into the upper one until a single row remains.

Dry Run Table

Input: 1 -> 2 -> 3 -> 4

Step	Action	State
1	Find Mid	`fast` moves `1 → 3 → NULL`; `slow` stops at `3`.
2	Split	The second half starts at `slow.next` (`4`); `slow.next = NULL` leaves `1->2->3` and `4`.
3	Reverse 2nd	`4` on its own is already reversed.
4	Merge	Splice `4` after `1`: `1->4->2->3`. `second` is now `NULL`.
Result	-	`1 -> 4 -> 2 -> 3`

For 1 -> 2 -> 3 -> 4 -> 5 the halves are 1->2->3 and 4->5, reversed to 5->4, and the merge gives 1 -> 5 -> 2 -> 4 -> 3.

The Solution Template

Three-step process.

Reorder List Code

1var reorderList = function(head) {
2    if (!head) return;
3    let slow = head, fast = head;
4    while (fast && fast.next) {
5        slow = slow.next;
6        fast = fast.next.next;
7    }
8    let prev = null, curr = slow.next;
9    slow.next = null;
10    while (curr) {
11        let temp = curr.next;
12        curr.next = prev;
13        prev = curr;
14        curr = temp;
15    }
16    let first = head, second = prev;
17    while (second) {
18        let tmp1 = first.next;
19        let tmp2 = second.next;
20        first.next = second;
21        second.next = tmp1;
22        first = tmp1;
23        second = tmp2;
24    }
25};

Edge Cases & Common Mistakes

Odd vs Even Length: Split logic must handle both.
Single Node: Should do nothing.
Null check: Return if head is null.

Summary

This problem combines three fundamental Linked List operations into one: Finding Middle, Reversing, and Merging.

Remove Nth Node From End of List

Swap Nodes in Pairs