Coding 2 - Odd Even Linked List

Problem: Odd Even Linked List Given the head of a singly linked list, group all nodes with odd indices (1-based) together followed by the nodes with even indices (1-based). Return the head of the reordered list. Note: “odd/even” refers to the node positions, not their values. Input/Output Input: head node head Output: head node of the reordered list Constraints 0 <= n <= 10^4 Node values can be any integers Expected: O(n) time and O(1) extra space Examples Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 3 -> 5 -> 2 -> 4 Input: 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 Output: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4 Example Input 5 1 2 3 4 5 Output 1 3 5 2 4