Odd Even Linked List
Medium · Linked Lists · Linked List
Problem
Given the head of a singly linked list, regroup it so that all nodes at odd positions come first, followed by all nodes at even positions. Positions are counted from 1, so the head is odd, the second node is even, and so on. This is about positions, not the values stored in the nodes.
Keep the relative order inside each group. Solve it in O(n) time with O(1) extra space, and return the head of the regrouped list.
Examples
Input: head = [10,20,30,40,50] Output: [10,30,50,20,40]
Positions 1, 3 and 5 hold 10, 30 and 50, and they are followed by positions 2 and 4.
Input: head = [1,2] Output: [1,2]
The single odd node already precedes the single even node.
Input: head = [4,7,1,8,6,3] Output: [4,1,6,7,8,3]
Positions 1, 3, 5 hold 4, 1, 6 and positions 2, 4, 6 hold 7, 8, 3, whatever the values are.
Constraints
- The list has between 0 and 10^4 nodes
- -10^6 <= Node.val <= 10^6
Approaches
- Baseline: collect the nodes, then relink — time O(n), space O(n)
Follow-up
What if you had to split the list into k groups by position modulo k? Keep k heads and k tails, append each node to tail i % k, and chain the groups at the end: still one pass and O(k) extra space.
Related problems
Start free on Cariara · Coding problems · System design studio
