Pattern visualizer
Swap Nodes in Pairs
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. 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]..
Iterative pointer rewiring behind a dummy node
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.
1FUNCTION swapPairs(head)2 dummy <- NEW NODE3 dummy.next <- head4 prev <- dummy5 WHILE prev.next != NULL AND prev.next.next != NULL6 first <- prev.next7 second <- first.next8 prev.next <- second9 first.next <- second.next10 second.next <- first11 prev <- first12 RETURN dummy.next
← / → step · space play · Home restart