Odd Even Linked List

Explanation & Solution

Description

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd (index 1), the second node is even (index 2), and so on.

Note that the relative order inside both the odd and even groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Input:head = [1,2,3,4,5]

Output:[1,3,5,2,4]

Explanation: Odd-indexed nodes: 1, 3, 5. Even-indexed nodes: 2, 4. Result: [1,3,5,2,4].

Constraints

The number of nodes in the list is in the range [0, 10⁴]
-10⁶ <= Node.val <= 10⁶

Approach

Fast and Slow Pointers pattern

1. Handle Edge Cases

If the list is empty or has only one node, return it as-is — no reordering is needed.

2. Initialize Pointers

Set odd to head (the first node, index 1).
Set even to head.next (the second node, index 2).
Save evenHead = even — we need this later to connect the two groups.

3. Reorder the List

Loop while even and even.next exist:
Link odd.next to even.next (skip over the even node to the next odd node).
Advance odd to odd.next.
Link even.next to odd.next (skip over the odd node to the next even node).
Advance even to even.next.
This weaves through the list, building two separate chains: one of odd-indexed nodes and one of even-indexed nodes.

4. Connect the Two Groups

After the loop, odd points to the last node in the odd chain.
Set odd.next = evenHead to attach the even chain after the odd chain.

Key Insight

By maintaining two separate chains and merging them at the end, we avoid any extra space beyond a few pointers.

Time

O(n)single pass through the list.

Space

O(1)only pointer variables are used (excluding the output array).

Visualization

Input:

Linked List Traversal

—

Press play to start traversal

Slow (S)Fast (F)Both

5 steps

Solution Code

Rotate List

Swap Nodes in Pairs