Swap Nodes in Pairs
Problem Statement
Given the head of a singly linked list, swap every two adjacent nodes and return the modified list. The node values must not be changed; only links may be rewired. If the list has an odd number of nodes, the final node remains in place.
Input
The head of a singly linked list, possibly empty.
Output
The head of the list after every adjacent pair has been swapped in place.
Constraints
- •
The number of nodes is in the range 0 to 100 - •
0 <= Node.val <= 100
Examples
Example 1
head = 1 -> 2 -> 3 -> 4
2 -> 1 -> 4 -> 3Example 2
head = 1 -> 2 -> 3
2 -> 1 -> 3Learning Objectives
- Recognise pair swapping as the **k = 2** version of fixed-size segment reversal.
- Use a dummy head and a **previous** pointer to reconnect each swapped pair.
- Update the three links of a pair in an order that never loses the remaining list.
- Explain why an odd trailing node should be left untouched.
Intuition
Pattern Recognition
The phrase swap every two adjacent nodes is a tiny in-place reversal problem repeated across the list. Each pair is a two-node segment: reverse it, reconnect the node before the pair, then move to the next pair. Because the head may change after the first swap, a dummy node keeps the code uniform.
The pointer trap is overwriting the link to the rest of the list. For each pair, name first = previous.next and second = first.next. Save the pair relationship before rewiring: first.next must become the node after second, second.next must become first, and previous.next must become second. After that, first is the tail of the swapped pair, so it becomes the new previous.
Common mistakes
- ×Swapping node values instead of rewiring nodes, which misses the linked-list pointer skill being tested.
- ×Forgetting to connect **previous.next** to the second node, causing the swapped pair to be unreachable from the head.
- ×Advancing **previous** to the second node after a swap; the correct next boundary is the first node, now the pair tail.
- ×Entering the loop when only one node remains and then reading **first.next** when it is null.
Algorithm Explanation
Key idea
Use previous as the stable node before the pair. Let first = previous.next and second = first.next. Rewire the pair so second comes before first, attach previous to second, and then move previous to first, which is now the tail of the swapped pair.
Pointer walkthrough
For head = 1 -> 2 -> 3 -> 4, start with dummy -> 1 -> 2 -> 3 -> 4 and previous = dummy. The first pair is first = 1 and second = 2. Set 1.next to 3, set 2.next to 1, and set dummy.next to 2, giving dummy -> 2 -> 1 -> 3 -> 4. Move previous to 1. The next pair is 3 and 4. After the same rewiring, the list is dummy -> 2 -> 1 -> 4 -> 3.
Algorithm
- Create dummy and set dummy.next to head.
- Initialise previous to dummy.
- While previous.next and previous.next.next both exist, identify first and second.
- Point first.next to the node after second.
- Point second.next to first, then point previous.next to second.
- Move previous to first and continue with the next pair.
- Return dummy.next.
Solutions
Solution 1: Iterative dummy-head pair swap
Use this as the primary interview solution because it runs in O(1) extra space and makes every pair reconnection explicit.
Process one adjacent pair at a time. The dummy node owns the head edge case, and previous always points to the node before the next pair. Rewire exactly three links, then advance to the tail of the swapped pair.
Step-by-step
- Create dummy and set previous to it.
- Continue only while two nodes exist after previous.
- Name the pair first and second so the rewiring order is readable.
- Connect first.next to the node after second to preserve the suffix.
- Place second before first and connect previous to second.
- Move previous to first, which is now the tail of the swapped pair.
- Return dummy.next.
O(n)
O(1)
Each node is visited a constant number of times and the algorithm stores only a few pointers.
Java implementation
Solution 2: Recursive pair swap
Use this when the interviewer asks for a recursive formulation or when explaining the self-similar structure matters more than constant stack space.
Swap the first two nodes, then recursively swap the rest of the list and attach that swapped suffix after the original first node. The recursion naturally leaves an empty list or a single trailing node unchanged.
Step-by-step
- If head is null or head.next is null, return head because there is no complete pair.
- Let second be head.next and remember the remaining suffix after second.
- Point second.next to head so the first pair is swapped.
- Set head.next to the result of recursively swapping the remaining suffix.
- Return second as the new head of this swapped pair.
O(n)
O(n)
Each node is processed once, and the recursion stack can contain one frame per pair.
Java implementation
Dry Run
Sample input
head = 1 -> 2 -> 3 -> 4. Track previous, the two nodes in the current pair, and the list after each swap.
| pair | previous before | first | second | list after swap | next previous |
|---|---|---|---|---|---|
| 1 | dummy | 1 | 2 | dummy -> 2 -> 1 -> 3 -> 4 | 1 |
| 2 | 1 | 3 | 4 | dummy -> 2 -> 1 -> 4 -> 3 | 3 |
| stop | 3 | none | none | dummy -> 2 -> 1 -> 4 -> 3 | no complete pair remains |
Each completed pair moves previous to the pair tail. After 4 -> 3, there are no two nodes after previous, so returning dummy.next gives 2 -> 1 -> 4 -> 3.
Interview Tips
Present this as the smallest segment-reversal template. Say that previous is the node before the segment, first becomes the tail, and second becomes the head. That framing makes the relationship to Reverse Nodes in k-Group obvious and helps avoid value-swapping shortcuts.
Likely follow-ups
- How does this generalise to reversing nodes in groups of **k**?
- How would you swap every other pair instead of every pair?
- How would the recursive solution behave on a very long list?
- How would you update the algorithm for a doubly linked list?
Similar Problems
Key Takeaways
- Swapping pairs is fixed-size segment reversal with **k = 2**.
- A dummy head handles changes to the real head after the first swap.
- After a pair swap, the original first node becomes the tail and the next **previous**.
- Always preserve the suffix by setting **first.next** before redirecting the pair head.