Odd Even Linked List

Intuition

Rather than shuffling values, we rewire the links so odd-position nodes form one chain and even-position nodes form another. We keep an odd pointer and an even pointer, plus a saved reference to the first even node so we can attach the even chain later. Walking forward, each pointer skips over its neighbor of the other parity, effectively splitting the list into two interleaved strands. When we run out of nodes, we simply connect the tail of the odd chain to the head of the even chain. Only a handful of pointers are used, so the space stays constant.

Algorithm walkthrough

1. 1If the list is empty, return it as is; otherwise set odd to head and even to head.next.
2. 2Remember evenHead, the first even-position node, so it can be reattached later.
3. 3While even and even.next exist, link odd.next to even.next and advance odd, then link even.next to odd.next and advance even.
4. 4This threads odd-position nodes together and even-position nodes together in order.
5. 5Finally set odd.next to evenHead so the even chain follows the odd chain, and return head.

Implementation

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        odd = head
        even = 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