DSA problem
Odd Even Linked List
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. Note that the indices here refer to the node's position (1-indexed), not the value stored inside the node.
The first node is considered odd, the second node is considered even, and so on. The relative order inside both the odd group and the even group must be preserved exactly as it appeared in the original list.
A naive solution might copy values into an array, rearrange them, and rebuild the list — but that uses O(n) extra space. The problem explicitly asks for an O(1) space, O(n) time solution, so we must rewire the existing pointers in place.
The key intuition is to maintain two separate chains while walking the list once: an odd chain and an even chain. We advance two pointers in lockstep, splicing every other node onto each chain. After the traversal, we remember the head of the even chain and simply attach it after the tail of the odd chain. Because each node is visited exactly once and only a constant number of pointers are used, this achieves the required complexity.
Examples
head = [1,2,3,4,5][1,3,5,2,4]head = [2,1,3,5,6,4,7][2,3,6,7,1,5,4]head = [1][1]Constraints
- The number of nodes in the linked list is in the range [0, 10^4].
- -10^6 <= Node.val <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.