Odd Even Linked List
Medium · Linked List · Explanation and code example
Separate Odd and Even Positions
How it works
Build two chains using the existing nodes: one for odd positions and one for even positions. Append nodes in their original order, terminate the even chain, and attach it after the odd chain. Only links change; node values are untouched.
Steps
- Alternate appending each node to the odd or even chain.
- Set the even tail next link to null.
- Attach the even head after the odd tail and return the odd head.
Complexity
- Time: O(n).
- Space: O(1).
Things to watch for
- Odd/even refers to positions, rather than values.
- Terminate the even chain to avoid a cycle.
- Empty and one-node lists need no special ordering.
Python code example
class Solution:
def oddEvenList(self, head: ListNode) -> ListNode:
oddHead = ListNode(0)
evenHead = ListNode(0)
odd = oddHead
even = evenHead
isOdd = True
while head:
if isOdd:
odd.next = head
odd = head
else:
even.next = head
even = head
head = head.next
isOdd = not isOdd
even.next = None
odd.next = evenHead.next
return oddHead.next
C++ code example
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
ListNode oddHead(0);
ListNode evenHead(0);
ListNode* odd = &oddHead;
ListNode* even = &evenHead;
for (int isOdd = 0; head; head = head->next)
if (isOdd ^= 1) {
odd->next = head;
odd = odd->next;
} else {
even->next = head;
even = even->next;
}
odd->next = evenHead.next;
even->next = nullptr;
return oddHead.next;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.