Use two dummy nodes to track the heads of the even/odd half links. Split and reconnect them. O(N) time and O(1) space.

```
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode *tail[2], dummyE(0), dummyO(0);
int i;
tail[0] = &dummyE;
tail[1] = &dummyO;
for(i=0;head!=nullptr;++i)
{
tail[i%2] = tail[i%2]->next = head; // split into two half
head = head->next;
}
tail[0]->next = dummyO.next; // reconnect the link
tail[1]->next = nullptr;
return dummyE.next;
}
};
```