DSA problem
Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values stored in the list's nodes — that is, only the node pointers themselves may be changed.
If the list has an odd number of nodes, the final lone node stays in place because it has no partner to swap with. The relative order of every pair is reversed, but the pairs themselves keep their original sequence relative to one another.
The classic pitfall is the head of the list: after the first swap the second node becomes the new head, so a simple loop that returns the original head would be wrong. A dummy node placed before the head elegantly removes this special case, because the dummy's next pointer always tracks the true head as it changes.
The intuition is to keep a prev pointer that sits just before each pair. For every pair of nodes (call them first and second), we rewire three links: prev.next points to second, first.next points to whatever follows second, and second.next points back to first. Then we advance prev to first (now the tail of the swapped pair) and repeat. This processes the list in a single pass with constant extra space.
Examples
head = [1,2,3,4][2,1,4,3]head = [1,2,3][2,1,3]head = [][]Constraints
- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.