LeetCode 328 · Linked list

Odd Even Linked List, explained with a picture

Odd coaches first, then even.

Linked list
▶ Watch it step by step

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 head

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.