EasyEditorial · 6 minGenerated by the editor · Aug 29
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Intuitionthe required order is already present inside two subsequences
The list positions form two subsequences: positions 1, 3, 5 and so on, followed by positions 2, 4, 6 and so on. Each subsequence already has the correct relative order, so you do not need to compare values or sort anything. You only need to separate neighboring nodes into an odd chain and an even chain while walking forward once.
Keep the first node of the even chain in evenHead before changing any links. During the walk, odd points to the last node currently in the odd chain and even points to the last node currently in the even chain. Each iteration moves one node from each original pair into its proper chain. When no complete pair remains, the odd tail is connected to evenHead.
Approach
1Return nullptr immediately for an empty list, because there is no first odd node from which to build either chain.
2Set odd to head, even to head->next, and save evenHead as head->next, because the odd chain starts at the original head while the even chain must remain reachable after its links change.
3While even and even->next both exist, connect odd->next to even->next and advance odd, because the node after the current even node is the next odd-position node and skipping this assignment would leave that node trapped in the old chain.
4Connect even->next to odd->next and advance even, because after odd advances, odd->next is the next even-position node; moving even in the same iteration keeps both tails aligned with their chains.
5Stop when there is no complete odd-even pair left, because either condition means there is no further odd node that can be extracted safely from after an even node.
6Connect odd->next to evenHead, because the odd chain is complete and the saved pointer is the first node of the stable even chain.
7Return head, which is still the first odd-position node and therefore the head of the reordered list; no new node or second traversal is needed.
Complexityconstant working memory even for the longest allowed list
MEASURE
BOUND
WHY
Time
O(n)
The loop advances odd and even through successive nodes, and each original node is rewired at most once. The traversal never moves backward or revisits a completed chain, so the total number of pointer operations is proportional to n.
Space
O(1) extra
Only odd, even, evenHead, and the method's fixed pointer variables are stored. The returned list reuses the input nodes and is required output, so it is excluded from extra space; the bound stays O(1) for empty, short, and maximally long lists.
CPPRewire the two stable chains in one pass and join them at the odd tail.
#include <cstddef>
using namespace std;
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head) return nullptr;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
The order of the two assignments inside the loop matters. First, odd->next is changed to the next odd node, and odd advances there. Only then can even->next read odd->next to find the next even node. Saving evenHead before the loop is equally important: the even pointer moves, but the final join always needs the chain's original first node.
Common mistakestwo pointer-link errors that can silently lose nodes