Group all nodes at odd indices together, followed by nodes at even indices, preserving relative order within each group. (LeetCode 328)
Brute force (extra space): collect odd-indexed values, then even-indexed values, into a list, then reassign them back onto the original nodes.
class Solution { public ListNode oddEvenList(ListNode head) { if (head == null) return null;
List<Integer> ll = new ArrayList<>(); ListNode temp = head;
while (temp != null && temp.next != null) { ll.add(temp.val); temp = temp.next.next; } if (temp != null) ll.add(temp.val); // for odd length lists, temp will be at the last node
temp = head.next;
while (temp != null && temp.next != null) { ll.add(temp.val); temp = temp.next.next; } if (temp != null) ll.add(temp.val); // for even length lists, temp will be at the last node
temp = head; int idx = 0;
while (temp != null) { temp.val = ll.get(idx); idx++; temp = temp.next; }
return head; }}Time: O(n). Space: O(n).
Optimal — in-place reordering: use two pointers, odd and even, tracking the tail of each
sub-list, plus evenHead so the even list can be appended once the odd list is done. Rearrange
the next pointers so odd nodes point to the next odd and even nodes point to the next even, then
connect the odd tail to evenHead.
class Solution { public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) return head;
ListNode odd = head; ListNode even = head.next; ListNode 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; return head; }}Time: O(n). Space: O(1).