Segregate Odd and Even Nodes in a Linked List

You are given the head of a finite acyclic singly linked list. Test cases display the node values as arrays, but the learner function receives a ListNode…

You are given the head of a finite acyclic singly linked list. Test cases display the node values as arrays, but the learner function receives a ListNode head. Rearrange the list so that every node sitting at an **even index** appears first, in its original order, followed by every node at an **odd index**, also in its original order. Return the rearranged list. Indices are **0-based**, so the head is at index 0 (an even-index node), the second node is at index 1 (odd), and so on. This is the classic "odd positions then even positions" grouping under 1-based numbering — under our 0-based convention that means even-index nodes first, then odd-index nodes. For example, `[1, 2, 3, 4, 5]` has even-index values 1, 3, 5 (indices 0, 2, 4) and odd-index values 2, 4 (indices 1, 3), so the result is `[1, 3, 5, 2, 4]`. The taught optimal approach runs in O(n) time and O(1) extra space by rewiring the existing next pointers instead of copying node values.

- `0 <= nodes.length <= 10^4` - `-10^6 <= nodes[i] <= 10^6` - Indices are 0-based: the head is index 0 (an even-index node). - The taught pointer-rewiring approach runs in O(n) time with O(1) extra space.

Example 1: input nodes = [1,2,3,4,5]; output [1, 3, 5, 2, 4]. Even-index values (indices 0,2,4) are 1, 3, 5; odd-index values (indices 1,3) are 2, 4.

Example 2: input nodes = [10,20,30,40]; output [10, 30, 20, 40]. Even-index values 10, 30 (indices 0,2) then odd-index values 20, 40 (indices 1,3).

Example 3: input nodes = [7]; output [7]. A single node sits at index 0 (even). There are no odd-index nodes, so the list is unchanged.

Category: Linked List. Topic: linked-list. Difficulty: Medium. Patterns: linked-list-traversal.