Reverse Linked List

Problem statement

A maintenance checklist is stored as a singly linked chain. For a return inspection, the technician wants to traverse the same checklist in the opposite direction, beginning at what used to be the final task. Your task Reverse the singly linked list and return its new head. Build a singly linked list from the input values and perform the operation on its nodes. Important details Change next pointers rather than merely printing a copied array backward. Each original node must remain exactly once. The original head becomes the tail and its next pointer becomes null. Use O(n) time and O(1) auxiliary space. Worked example The checklist 2 -> 7 -> 9 becomes 9 -> 7 -> 2. The new head holds 9, and the node holding 2 has no successor.

Input format

The first line contains n. The next line contains n space-separated integers; for n = 0 this line may be empty.

Output format

Print the resulting values in order, separated by spaces. Print EMPTY if there are no values.

Constraints

0 <= n <= 5000; -5000 <= values <= 5000.

Sample input

3
2 7 9

Sample output

9 7 2