Swap the neighbours
Swap every two neighbouring nodes by rewiring three links per pair, not by swapping the values. About 15 minutes.
A pair in the middle of the chain
Look at one pair, a and b, with the box before it (prev) and the box after it. Before: prev → a → b → rest. We want prev → b → a → rest.
Three pointers change. a must point at the rest. b must point at a. And prev must point at b. A dummy node stands before the whole list so that the first pair has a prev too.
a = prev.next b = a.next a.next = b.next b.next = a prev.next = b
Prev is the dummy before box 1. The pair is a = 1 and b = 2.
The order and the loop
Do the changes in this order: a first, then b, then prev. Each uses a pointer that hasn't been overwritten yet. After the swap, a is at the end of the pair, so move prev to a to be ready for the next pair.
Keep going while there are two boxes left after prev. If one box or none remains, the last box stays where it is.
dummy = ListNode(0, head)
prev = dummy
while prev.next and prev.next.next:
a = prev.next
b = a.next
a.next = b.next
b.next = a
prev.next = b
prev = a
return dummy.nextA list has 5 nodes. What happens to the last node?
- AIt stays in place, since it has no partner
- BIt is swapped with the first node
- CIt is removed
Show the answer
It stays in place, since it has no partner. The loop needs two nodes after prev, so a lone last node is left alone.
Swap neighbours
Given the head of a singly linked list, swap every two neighbouring nodes (the first with the second, the third with the fourth, and so on) and return the new head. Swap the nodes themselves by changing links; do not just exchange values. If the list has an odd length, the last node stays where it is.
head = [1, 2, 3, 4] → [2, 1, 4, 3]
0 ≤ number of nodes ≤ 5,000 · -1,000,000 ≤ node.val ≤ 1,000,000