Linked List Segment Reordering by Parity Length

You are given a singly linked list of integers.

Step 1: Segment Formation

• Divide the list into contiguous segments such that:

  • Each segment contains only even values OR

  • Each segment contains only odd values

Step 2: Apply Transformation on Each Segment

For each segment:

• If the length is even → Reverse the segment

• If the length is odd → Rotate the segment to the right by one position

Important Rules:

• Maintain the relative order of segments

• Perform all operations in-place

• Return the head of the modified linked list

📥 Input Format

• Head of a singly linked list

• Nodes represented as: value → value → value → ...

📤 Output Format

• Modified linked list after applying transformations

⚙️ Constraints

• 1≤N≤1000001 \le N \le 1000001≤N≤100000

• 1≤Node value≤100001 \le \text{Node value} \le 100001≤Node value≤10000

🧪 Examples

Example 1

Input:

1 → 3 → 5 → 2 → 4 → 6

Output:

5 → 1 → 3 → 6 → 2 → 4

Explanation:

• Segment 1: [1,3,5] (odd values, length = 3 → rotate right)

• Segment 2: [2,4,6] (even values, length = 3 → rotate right)