A complete visual walkthrough of pointer rewiring in a linked list — from brute force to clean iterative solution.
The most obvious approach: just swap the values of each pair of nodes. Walk through two at a time and exchange their data.
// Tempting but VIOLATES the constraint! while (curr != null && curr.next != null) { int temp = curr.val; curr.val = curr.next.val; // swap values curr.next.val = temp; curr = curr.next.next; }
This looks clean and runs in O(n), but the problem explicitly says: "You must solve it without modifying the values in the nodes."
Why this constraint? In real systems, nodes carry complex payloads (not just integers). Swapping pointers is O(1) regardless of data size. Swapping values could be expensive or impossible if the data is immutable. The constraint teaches you proper pointer manipulation — a fundamental linked list skill.
We need to actually rewire the pointers so the nodes physically change position in the list. This is where the dummy node technique shines.
We create a dummy node pointing to the head, then use a prev pointer to rewire each pair. For every pair of adjacent nodes (first and second), we perform exactly three pointer changes:
Let's see the before and after of rewiring a single pair:
After the swap, prev advances to first (now at position 2), and we repeat for the next pair.
Why a dummy node? The head of the list changes after the first swap (node 2 becomes the new head). A dummy node lets us treat the head swap exactly like any other swap — no special cases needed. We just return dummy.next at the end.
Let's trace through the complete algorithm for the input [1, 2, 3, 4] step by step.
Create a dummy node pointing to the head. Set prev = dummy.
first = prev.next = 1, second = prev.next.next = 2
Apply the three rewires:
Pair (1,2) is swapped. Advance: prev = first (prev moves to node 1).
first = prev.next = 3, second = prev.next.next = 4
Apply the three rewires:
Both pairs are swapped. prev.next (node 3) has no next pair, so the loop exits. Return dummy.next.
The algorithm handles all edge cases naturally through its loop condition: prev.next != null && prev.next.next != null.
null.prev.next.next is null.No special-case code needed. The while-loop condition prev.next != null && prev.next.next != null naturally stops when there are fewer than two nodes remaining. A single trailing node is simply left untouched.
class Solution { public ListNode swapPairs(ListNode head) { // Dummy node simplifies head-swap edge case ListNode dummy = new ListNode(0, head); ListNode prev = dummy; // Keep going while there are at least 2 nodes ahead while (prev.next != null && prev.next.next != null) { // Identify the pair ListNode first = prev.next; // 1st node of pair ListNode second = prev.next.next; // 2nd node of pair // === Three pointer rewires === first.next = second.next; // first skips over second second.next = first; // second points back to first prev.next = second; // prev connects to second (new front) // Advance prev to first (now 2nd in the pair) prev = first; } return dummy.next; // dummy.next is the new head } }
Order matters! The three assignments must happen in this exact sequence. If you set prev.next = second first, you lose the reference to first. If you set second.next = first before saving second.next, you lose the rest of the list. Think of it as: save the tail, link backward, then connect from the front.
Enter list values and step through the pair-swapping algorithm. Watch the pointer rewiring happen node by node.
We traverse the list once, processing two nodes per iteration. Each swap involves exactly three pointer assignments — constant work. The only extra memory is the dummy node and a few pointer variables.
Recursive alternative: A recursive solution is elegant but uses O(n/2) = O(n) stack space. The iterative approach here achieves true O(1) space, which is optimal for linked list manipulation problems.