Odd places first, even places after
Regroup a list so the nodes in odd places come first, then the nodes in even places, with two pointers weaving the chain apart. About 14 minutes.
Skip over your neighbour
Think of nodes in places 1, 2, 3, 4, 5. Odd places are 1, 3, 5 and even places are 2, 4. Each odd node can point past its even neighbour to the next odd node, and each even node can point past the next odd node to the next even node.
Two pointers do this together, odd and even, taking turns. The list unzips into two chains that stay in their original order.
cur = head
while cur and cur.next:
# skip a neighbour
cur = cur.next.nextOdd is on place 1 and even is on place 2. Save place 2 as the even start.
Save the even start
While the odd chain grows, the even chain's first node stops being reachable from the head. Before relinking, store a link to it.
The loop continues while the even pointer and its next both exist. When it ends, the odd pointer is on the last odd node. Point it at the saved even start, and the two chains become one list.
# where chain 2 starts second_head = head.next
Why does the loop test both the even pointer and the node after it?
- AThe even node must exist, and so must the node after it, so the odd pointer has somewhere to skip to
- BTo make the even pointer move faster
- CTo keep the values sorted
Show the answer
The even node must exist, and so must the node after it, so the odd pointer has somewhere to skip to. Each round steps over a node, so two nodes must be available.
Odd even linked list
Given the head of a singly linked list, group all the nodes in odd places (the 1st, 3rd, 5th, and so on) together, followed by the nodes in even places. The relative order inside each group must be kept. Do it by relinking nodes, with no extra list. The places refer to node positions, not to values.
head = [1, 2, 3, 4, 5] → [1, 3, 5, 2, 4]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000