Swap Nodes in Pairs
MediumRelink each pair, keep the predecessor
Problem
Given a linked list, swap every two adjacent nodes and return its head (swap the nodes themselves, not just the values).
Swap every two neighbouring nodes by relinking their pointers.
The idea
For each adjacent pair, point the predecessor at the second node, the second at the first, and the first at whatever follows the pair. A dummy head gives the first pair a predecessor so the loop body never needs a special case.
The trick
- Swap the links, not the values, if the problem forbids value swaps.
- A trailing odd node is left alone — the loop needs two nodes to proceed.
- O(n) time, O(1) space.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — head = [1, 2, 3, 4] Values: 1, 2, 3, 4.
1dummy = Node(next=head); prev = dummy2while prev.next and prev.next.next:3 a = prev.next; b = a.next4 a.next = b.next; b.next = a; prev.next = b5 prev = a6return dummy.nextInput
- array
- [1, 2, 3, 4]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4
- Output:
- 2 -> 1 -> 4 -> 3
- Explanation:
- Each adjacent pair swaps → 2,1,4,3.
Example 2
- Input:
- list = 1 -> 2 -> 3
- Output:
- 2 -> 1 -> 3
- Explanation:
- Last lonely node stays.
Example 3
- Input:
- list = 1
- Output:
- 1
- Explanation:
- Nothing to swap.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.