DSA Tracker

Visualize

Swap Nodes in Pairs

Iterative pointer rewiring behind a dummy node

time O(n)space O(1)

Swapping two neighbouring nodes touches three links: the one coming into the pair, the one between the two nodes, and the one leaving the pair for the rest of the list. The pointer that comes into the first pair is the head itself, which would make pair one a special case — so a dummy node is placed before head and prev starts there, making every pair identical. For each pair, prev is pointed at second, first is pointed at whatever followed second, and only then is second pointed back at first; do the last of those first and the tail is lost. After the swap, first is the back of the pair, so prev moves onto it. An odd trailing node never satisfies the loop condition and is left alone.

Details

Animated on: head = [1, 2, 3, 4, 5, 6, 7]. Swap every two adjacent nodes by relinking them (not by swapping values) and return the new head. Answer: [2, 1, 4, 3, 6, 5, 7].

Problem:Swap Nodes in PairsMedium

Pattern:Linked List Manipulation

Iterative pointer rewiring behind a dummy node

step 1 / 11

1
[0]
2
[1]
3
[2]
4
[3]
5
[4]
6
[5]
7
[6]

List [1, 2, 3, 4, 5, 6, 7], 7 nodes. A dummy node is placed in front of head and prev starts there, so the very first pair is rewired by the same three assignments as every later pair — without it, swapping nodes 0 and 1 would need a special case to change head.

Pseudocode
1FUNCTION swapPairs(head)
2  dummy <- NEW NODE
3  dummy.next <- head
4  prev <- dummy
5  WHILE prev.next != NULL AND prev.next.next != NULL
6    first <- prev.next
7    second <- first.next
8    prev.next <- second
9    first.next <- second.next
10    second.next <- first
11    prev <- first
12  RETURN dummy.next

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. List [1, 2, 3, 4, 5, 6, 7], 7 nodes. A dummy node is placed in front of head and prev starts there, so the very first pair is rewired by the same three assignments as every later pair — without it, swapping nodes 0 and 1 would need a special case to change head.
  2. Pair 1: first=1 and second=2 both exist, so there is a whole pair to swap. second.next=3 is the tail that must survive the swap. Three links change: prev into the pair, the link between the two, and the link out to the tail.
  3. Rewired: dummy.next <- 2, then first.next <- 3, then second.next <- 1. The list now reads [2, 1, 3, 4, 5, 6, 7]. Order matters: first.next must take the tail before second.next is overwritten, or the nodes after the pair become unreachable.
  4. prev <- first (1), which after the swap is the SECOND node of the pair and therefore the node directly before the next pair. Its next link is what the next iteration rewires.
  5. Pair 2: first=3 and second=4 both exist, so there is a whole pair to swap. second.next=5 is the tail that must survive the swap. Three links change: prev into the pair, the link between the two, and the link out to the tail.
  6. Rewired: prev=1.next <- 4, then first.next <- 5, then second.next <- 3. The list now reads [2, 1, 4, 3, 5, 6, 7]. Order matters: first.next must take the tail before second.next is overwritten, or the nodes after the pair become unreachable.
  7. prev <- first (3), which after the swap is the SECOND node of the pair and therefore the node directly before the next pair. Its next link is what the next iteration rewires.
  8. Pair 3: first=5 and second=6 both exist, so there is a whole pair to swap. second.next=7 is the tail that must survive the swap. Three links change: prev into the pair, the link between the two, and the link out to the tail.
  9. Rewired: prev=3.next <- 6, then first.next <- 7, then second.next <- 5. The list now reads [2, 1, 4, 3, 6, 5, 7]. Order matters: first.next must take the tail before second.next is overwritten, or the nodes after the pair become unreachable.
  10. prev <- first (5), which after the swap is the SECOND node of the pair and therefore the node directly before the next pair. Its next link is what the next iteration rewires.
  11. prev=5 has a next (7) but no next.next — a lone node cannot form a pair, so the loop condition fails and 7 stays in place. Answer: [2, 1, 4, 3, 6, 5, 7], returned as dummy.next so the new head (2) needs no special handling.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Swap Nodes in Pairs in the editorAll Linked List problemsBack to roadmap