Odd Even Linked List

Medium · Linked Lists · about 15 minutes

Asked at Apple, Amazon, Google, Meta, Microsoft.

Given the head of a linked list, group all nodes at odd positions (1st, 3rd, 5th, …) first, followed by the nodes at even positions, keeping the relative order inside each group. Use O(1) extra space and O(n) time, and return the reordered list.