Segregate Odd-Even Problem Statement

In a wedding ceremony at NinjaLand, attendees are blindfolded. People from the bride’s side hold odd numbers, while people from the groom’s side hold even numbers. For the game to start quickly, all the bride’s side people should come first, followed by the groom’s side people, maintaining their original order.

Explanation:

The attendees are represented as a singly linked list, and you need to rearrange the list such that all odd-numbered attendees appear before the even-numbered ones, preserving the order of appearance.

Input:

The first line contains an integer T, the number of test cases.
Each test case consists of a single line of integers representing the linked list, separated by spaces, and terminated by -1.
-1 is not a part of the list.

Output:

For each test case, output the rearranged list with odd numbers first, followed by even numbers, separated by spaces and terminated by -1.
Each test case should be printed on a new line.

Example:

Input:

1
1 4 3 -1

Output:

1 3 4 -1

Explanation:

In the example, the input list is 1 -> 4 -> 3. After rearranging, it becomes 1 -> 3 -> 4, with odd numbers first.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5 * 10⁴
• 0 <= data <= 10⁴ and data != -1
• Time Limit: 1 sec

Note:

You don't need to print the output; it has already been handled. Just implement the function.