Coding - Odd Even Linked List

Problem Statement: Odd Even Linked List

Problem Description: Given the head of a singly linked list, group all nodes at odd indices together followed by the nodes at even indices, and return the reordered list. The first node is considered odd, the second node is even, and so on. Preserve the relative order within both groups.

Examples:

1. Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]

2. Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]

Constraints:

• The number of nodes in the linked list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5

Hints:

• You can use the two-pointer technique to solve this problem. One pointer can be used to traverse the odd nodes, and the other to traverse the even nodes. After that, you can connect the two lists.

Explanation: To solve this problem, you can iterate through the linked list and separate the nodes at odd and even indices into two separate lists. Then, append the even list to the end of the odd list to get the final reordered list.

Here is a step-by-step approach:

1. Initialize two dummy nodes, odd and even, to represent the start of the odd and even linked lists, respectively.
2. Initialize two pointers, oddPtr and evenPtr, to the head of the original list.
3. Iterate through the original list, and for each node:
   • If the index is odd, append the node to the odd list and move oddPtr to the next node.
   • If the index is even, append the node to the even list and move evenPtr to the next node.
4. After the iteration, connect the end of the odd list to the start of the even list.
5. Return the head of the odd list, which is the reordered list.

This approach ensures that the relative order within both the odd and even groups is preserved, and the problem constraints are satisfied.