Reverse a Linked List

You are given a singly linked list defined by a sequence of node values. Your task is to reverse the linked list using pointer manipulation and output both the new head node's value and the list of node values in reversed order. If the list is empty, output None on the first line, followed by an empty second line.

The reversal should be accomplished in O(n) time with O(1) auxiliary space (excluding the space used for output). Formally, if the original list is represented as \(L = [a_1, a_2, \ldots, a_n]\), then after reversal the new list is \(L' = [a_n, a_{n-1}, \ldots, a_1]\). You are required to return both \(a_n\) (the new head node's value) and the sequence \(L'\) as the list of values.

inputFormat

The input is read from standard input. The first line contains an integer \(n\) (where \(n \ge 0\)) representing the number of nodes in the list. If \(n > 0\), the second line contains \(n\) space-separated integers indicating the node values in the order they appear in the original list.

outputFormat

Output to standard output two lines:

• The first line should contain the value of the new head node of the reversed linked list, or None if the list is empty.
• The second line should contain the node values of the reversed linked list separated by a space. If the list is empty, output an empty line.

## sample

5
1 2 3 4 5

5
5 4 3 2 1

</p>