The problem
Group all nodes at odd positions first, then all nodes at even positions, keeping each group’s order.
Input: 2 → 1 → 3 → 5 → 6 → 4 → 7 Output: 2 → 3 → 6 → 7 → 1 → 5 → 4
Picture it
Picture splitting a train into two smaller trains: coaches 1, 3, 5, … and coaches 2, 4, 6, …, by recoupling each coach to the one two places ahead. At the end, the odd train is coupled to the front of the even train.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Two running tails (odd, even), then link odd tail to even head. O(n), O(1).
Python solution
def odd_even(head):
if not head:
return head
odd, even = head, head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return headIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.