Swap Nodes in Pairs

Given a singly linked list, swap every two adjacent nodes and return its head after performing the swaps. You must change the pointers between nodes rather than swapping the node values.

The process should run in \(O(n)\) time and use \(O(1)\) extra space. Formally, given a linked list \(L_0 \rightarrow L_1 \rightarrow L_2 \rightarrow L_3 \rightarrow \cdots\), the list should be transformed into \(L_1 \rightarrow L_0 \rightarrow L_3 \rightarrow L_2 \rightarrow \cdots\).

If the list contains an odd number of nodes, the final node remains unchanged. The input is provided as a sequence of integers representing node values.

inputFormat

The input begins with an integer \(n\) on the first line representing the number of nodes in the linked list. The second line contains \(n\) space-separated integers representing the values of the nodes. If \(n = 0\), the list is empty.

outputFormat

Output the node values after swapping every two adjacent nodes, separated by spaces. If the list is empty, print an empty line.

## sample

4
1 2 3 4

2 1 4 3

</p>