Given the head of a singly linked list, rearrange the nodes so that all nodes at odd indexes appear first, followed by all nodes at even indexes.

• The first node in the list is considered at odd index 1, the second at even index 2, and so on.

• Within the odd group and the even group, the relative order of the nodes must remain the same as in the original list.

Return the head of the reordered linked list.

Note: You must solve the problem in $O(1)$ extra space complexity and $O(n)$ time complexity.

Constraints:

• The number of nodes in the linked list is in the range $[0, 10^3]$.

• $-10^3 \leq$ Node.val $\leq 10^3$

This problem requires us to reorder a singly linked list by grouping all odd-indexed nodes, followed by all even-indexed nodes. The key constraints are to perform this modification in place, using $O(1)$ extra space and in $O(n)$ time while preserving the original relative order within the odd and even groups.

The solution’s essence is to partition the linked list into two separate lists, one for odd-indexed nodes and one for even-indexed nodes, and then link them together. This is done in place by carefully reassigning the next pointers.

We establish three key pointers to manage the process:

• We use an odd pointer starting at head (the first node) and an even pointer starting at head.next (the second node).

• We also save the head of the even list (evenHead = head.next) because we’ll need to connect the end of the odd list to it later.

The following steps can be performed to implement the algorithm above:

1. We use an odd pointer starting at head (the first node) and an even pointer starting at head.next (the second node).

2. We also save the head of the even list (evenHead = head.next) because we’ll need to connect the end of the odd list to it later.

3. We traverse the linked list, and in each step, we re-link the nodes:

   1. The current odd node’s next is set to skip the adjacent even node and point to the next odd node (odd.next = even.next).

   2. The current even node’s next is set to skip the new adjacent odd node and point to the next even node (even.next = odd.next).

4. This process effectively unlinks the even nodes from the odd chain and links them into their own chain, while simultaneously connecting the odd nodes.

5. After the loop terminates, the odd pointer will be at the tail of the odd-indexed list.

6. We connect this tail to the saved head of the even-indexed list (odd.next = evenHead). This rewires the entire list in-place to meet the problem’s requirements.

Let’s look at the following illustration to get a better understanding of the solution: