Segregate Odd-Even Problem Statement

In a wedding ceremony at NinjaLand, attendees are divided into two groups: bride’s side and groom’s side. Attendees from the bride’s side hold odd numbers, while those from the groom’s side hold even numbers. Your task is to rearrange them so that all attendees from the bride’s side come first, followed by those from the groom’s side, while maintaining the original order within each group.

Input:

The first line contains an integer T, the number of test cases. Each test case consists of a single line with elements of a singly linked list separated by spaces and terminated with -1.

Output:

For each test case, output the bride’s side attendees followed by the groom’s side attendees, separated by spaces and terminated by -1, each test case output on a new line.

Example:

Input:

1 4 3 -1

Output:

1 3 4 -1

Explanation:

The input is a linked list 1 -> 4 -> 3. After rearranging, the list becomes 1 -> 3 -> 4, maintaining the original order of odd and even elements.

Constraints:

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

Note:

You don't need to print anything; just implement the function as the printing is already handled.