Given the head of a singly linked list, swap every pair of adjacent nodes and return the head. The first node swaps with the second, the third with the fourth, and so on. A leftover last node stays where it is. Swap the nodes themselves; do not just exchange the values stored in them.
Examples
Input: head = 1 -> 2 -> 3 -> 4
Output: 2 -> 1 -> 4 -> 3
Input: head = 1 -> 2 -> 3
Output: 2 -> 1 -> 3
Constraints
0 <= number of nodes <= 10**4- Target: O(n) time, O(1) extra space
Goals
- Rewire three pointers to swap two adjacent nodes
- Advance by two nodes per step and stop cleanly on an odd tail