LeetCode problem #24–Swap nodes in pairs (JavaScript)

In this LeetCode challenge, we’re asked to create a function that takes a LinkedList and swaps each of its ListNode elements in pairs. In other words, if the LinkedList’s values start as [1, 2, 3, 4] our function should change it to [2, 1, 4, 3].

The reason this challenge isn’t incredibly easy is because of the way in which we swap ListNodes. Unlike arrays, ListNodes require updating once swapped, to ensure that their .next pointers are correct. What this mans is that in order to swap 2 ListNodes, the following must take place (note that when I say “point” in these instructions, I am referring to that node’s .next value):

1. The node before the nodes being swapped must point to node 2
2. Node 2 must now point to node 1
3. Node 1 must now point to node 3

For both of the below solutions, we initialise a “dummy” list, which is a copy of the original LinkedList, with a dummy node added to its head. This allows us to manipulate what was originally the first ListNode easily, and we can then chop off this dummy node at the end by returning the dummy LinkedList’s .next property.

Solution #1: While loop

In this solution, we initialise a copy of the original LinkedList which we will use to traverse it, swapping as we go. We then run a while loop for so long as there remain 2 or more elements in the new LinkedList, as 2 are required in order to perform a swap.

Finally, we swap the 2 nodes, traverse 2 nodes further into the LinkedList, and the process repeats.

Solution #2: Recursive

This approach is more or less identical to the while loop, but is slightly more concise. The performance differences between the two approaches in JavaScript are negligible.