#328
Odd Even Linked List
Medium Two chains, then join
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reorder a linked list so all nodes at odd positions (1st, 3rd, …) come first, followed by nodes at even positions, keeping relative order. O(1) extra space.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: all odd-position nodes first, then even-position nodes.
Why this works: build two chains while walking, then attach the even chain after the odd one.
Example: 1→2→3→4→5
odd: 1→3→5, even: 2→41→3→5→2→4
✦Hints open one at a time
Build two chains as you walk: odd and even.
Remember the head of the even chain to attach it at the end.
↗Approach
odd = head, even = head.next, evenHead = even. While even and even.next exist, link odd to even.next and even to odd.next. Finally odd.next = evenHead.
</>Solution (Java)
/**
* class ListNode { int val; ListNode next; } // provided by LeetCode
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead; // odds first, then evens
return head;
}
}!Common mistake
Losing the even chain's head, so it can't be attached at the end.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Linked List
🎬 Episodes 40–45: video coming soon