Swap Nodes in Pairs - Video Solutions

Problem Overview: You receive the head of a singly linked list and must swap every two adjacent nodes. The swap must change node pointers, not node values. For example, 1→2→3→4 becomes 2→1→4→3. If the list length is odd, the final node remains unchanged.

Approach 1: Iterative Pointer Manipulation (O(n) time, O(1) space)

This approach walks through the list while swapping nodes in pairs using pointer updates. Maintain a dummy node before the head to simplify edge handling. For each pair, identify first and second, then update three pointers: connect the previous node to second, point first.next to the node after the pair, and set second.next to first. Move the pointer forward by two nodes and repeat. Every node is visited once, giving O(n) time with constant extra memory O(1). This is the most practical technique when working with linked list pointer manipulation.

Approach 2: Recursive Pair Swapping (O(n) time, O(n) space)

The recursive solution treats the list as a sequence of pairs. The base case occurs when the list has zero or one node remaining. For each recursive call, swap the first two nodes: let second become the new head of the pair, then recursively process the remaining list starting from head.next.next. After the recursive call returns, attach the result to head.next. Each call processes exactly one pair, so the algorithm still runs in O(n) time. The recursion stack stores up to n/2 calls, resulting in O(n) auxiliary space. This version highlights structural thinking often used in recursion problems involving linked structures.

Recommended for interviews: The iterative pointer solution is usually the expected answer. Interviewers want to see that you can safely manipulate linked list pointers without breaking the chain. The recursive version demonstrates good conceptual understanding of pairwise decomposition, but the iterative approach is preferred because it avoids stack overhead and keeps space complexity at O(1).