Swap Nodes in Pairs
Medium · Backtracking · Linked List · Recursion
Problem
Given the head of a singly linked list, swap every two adjacent nodes and return the head of the new list. The first node trades places with the second, the third with the fourth, and so on. If the list has an odd number of nodes, the last one stays where it is.
Rearrange the nodes themselves by changing their next links; do not just swap the values stored in them.
Examples
Input: head = [1,2,3,4,5] Output: [2,1,4,3,5]
Pairs (1, 2) and (3, 4) swap; the 5 has no partner and stays last.
Input: head = [] Output: []
An empty list has nothing to swap.
Input: head = [7] Output: [7]
A single node has no partner.
Constraints
- 0 <= number of nodes <= 100
- 0 <= Node.val <= 100
Approaches
- Recursive: swap the first pair, then the rest — time O(n), space O(n) for the call stack
Follow-up
Swapping in pairs is reversing groups of two. The same dummy-node walk, with a small reversal inside each group, reverses groups of any size k. Ask yourself what changes when the last group is shorter than k.
Related problems
Start free on Cariara · Coding problems · System design studio
