Reverse linked list

Problem Description

You are given a linked list that contains integers. You have performed the following reverse operation on the list:

1. Select all subparts of the list that contain only even integers.
   For example, if the list is [1, 2, 8, 9, 12, 16], then the selected subparts will be [2, 8] and [12, 16].

2. Reverse each selected subpart.
   For example, [2, 8] becomes [8, 2] and [12, 16] becomes [16, 12].

Your task is to retrieve the original list from the modified one.

Linked List Definition

You should use the following definition of the linked list for this problem:

class Node {
    Object data;
    Node next;
}

Input Format

• The first line contains an integer n, the number of elements in the linked list.
• The second line contains n space-separated integers denoting the elements of the modified (reversed) list.

Output Format

Print the n elements of the original list (before the reverse operation), space-separated.

Constraints

• 1 ≤ n ≤ 10⁵
• List elements are integers.

Sample Input

9
2 18 24 3 5 7 9 6 12

Sample Output

24 18 2 3 5 7 9 12 6

Explanation

In the sample, the original list is:

24 18 2 3 5 7 9 12 6

After reversing the even subparts: - [24, 18, 2] → [2, 18, 24] - [12, 6] → [6, 12]

The resulting list becomes:

2 18 24 3 5 7 9 12 6

which matches the given input.

Approach

1. Traverse the linked list.
2. Whenever you encounter a contiguous segment of even numbers, reverse that segment.
3. Continue until the end of the list.
4. Print the reconstructed list.