Swap Nodes in Pairs

Intuition

Every pairwise swap on a linked list reduces to handling the first two nodes and trusting recursion for the remainder. If there are fewer than two nodes left, there is nothing to swap, so we return what we were given. Otherwise the second node becomes the new head of this segment. We point the original first node's next at whatever the recursive call produces for the rest of the list, then let the second node point back to the first. Returning the second node hands the correct new head up to the previous level of recursion.

Algorithm walkthrough

1. 1Base case: if the list is empty or has a single node (head or head.next is null), return head unchanged because a pair cannot be formed.
2. 2Capture the second node with second = head.next; it will become the head of this two-node segment after the swap.
3. 3Recurse on second.next, which is the rest of the list beyond the current pair, and store the returned head in head.next.
4. 4Set second.next = head so the second node now precedes the first, completing the local swap.
5. 5Return second, the new head of this segment, so the caller can wire it into the list correctly.

Implementation

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        second = head.next
        head.next = self.swapPairs(second.next)
        second.next = head
        return second