• The number of nodes is in the range [0, 10,000]
• -1,000,000 <= Node.val <= 1,000,000
• Must solve in **O(1) extra space** and **O(N) time**.

We must regroup a list by position: all nodes sitting at odd indices (1st, 3rd, 5th...) come first, then all nodes at even indices (2nd, 4th, 6th...), and inside each group the original order is kept. Read the word carefully — this is about where a node sits, not its value. In [2,1,3,5,6,4,7] the odd-position nodes are 2, 3, 6, 7 (values are irrelevant), and they end up ahead of 1, 5, 4.

The obvious plan: walk the list, drop odd-position nodes into one array and even-position nodes into another, then chain them together. It's correct and easy to reason about, but it spends O(N) extra space on the two buffers — and the problem explicitly demands O(1) space. The buffers exist only to hold nodes aside until we know both groups; if we could grow the two groups in place as we walk, we wouldn't need them at all.

Notice that odd-position and even-position nodes already alternate in the original list: odd, even, odd, even. So a node's next-of-the-same-parity is simply its neighbor's neighbor — two hops away. That means we can grow two separate chains simultaneously without any buffer: an odd chain and an even chain, each advancing by "skip over the other parity." Every node stays exactly where it lives in memory; we only re-point arrows so that odds link to odds and evens link to evens. At the end we bridge the two chains: the tail of the odd chain points to the head of the even chain.

We keep an odd pointer (writing the odd chain, starting at the head) and an even pointer (writing the even chain, starting at the second node). Crucially we also save even_head — the first even node — before the loop, because once we start rewiring we'll need it to perform the final bridge, and it will no longer be reachable as head.next.

if not head or not head.next:
    return head                 # 0 or 1 node: nothing to regroup

odd = head
even = head.next
even_head = even                # SAVE the even chain's head for the bridge

while even and even.next:
    odd.next = even.next        # odd links to the next odd (skip the even)
    odd = odd.next
    even.next = odd.next        # even links to the next even (skip the new odd)
    even = even.next

odd.next = even_head            # bridge: odd tail -> start of even chain
return head

Cost is one pass and a handful of pointers: O(N) time, O(1) space. The reusable idea is splitting one list into two by walking once and routing each node into the correct chain, then joining the chains — no buffers, because the nodes never move, only the arrows do. Hold onto each chain's head (to bridge) and each chain's tail (to append), and remember the tail-null-termination discipline. You'll apply the very same braid, routed by a value test instead of by parity, in Partition List.