Swap Adjacent Node Pairs

You are given the head of a linked list, head.

Swap every two adjacent nodes: the 1st and 2nd nodes trade places, the 3rd and 4th nodes trade places, and so on. If the list has an odd number of nodes, the last node keeps its position.

Return the head of the list after swapping.

Note that only the nodes themselves may be rearranged: the value stored in each node must not change.

Linked List Encoding

Your function receives head as a ListNode (or null for the empty list) and returns the head of the resulting list. The node type is provided for you, with val and next fields; you may relink the existing nodes in place.

The examples below write a list as the array of its values in order, so [1,2,3,4] is the list 1 -> 2 -> 3 -> 4. That is only how lists are displayed; the encoding and decoding are done for you.

Examples

Example 1

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation: 1 and 2 trade places, then 3 and 4 trade places.

Example 2

Input: head = []
Output: []
Explanation: The empty list has no pairs to swap.

Example 3

Input: head = [1]
Output: [1]
Explanation: A single node has no partner, so it keeps its position.

Example 4

Input: head = [1,2,3]
Output: [2,1,3]
Explanation: 1 and 2 trade places; 3 has no partner, so it keeps its position.