Can You Swap Nodes in Paris?

When discussing the concept of swapping nodes in a linked list, one common interview problem arises: the swapping of nodes positioned at certain intervals. A classic illustration of this problem can be framed using a fictitious scenario involving nodes in Paris. Let's break this down clearly.

Imagine you're navigating through a city mapped as a linked list, where each node represents a location. Our aim is to swap certain nodes based on specified intervals, for instance, swapping every two adjacent nodes. This concept is commonly referred to as "swapping nodes in pairs."

To illustrate this with code, here's how you can implement it in Python:

PythonCopy code

In the code above, we define a ListNode class to represent each node in our linked list. The swapPairs function takes the head of the linked list as an argument and performs the swapping of nodes in pairs.

Here is how the function operates:

1. A dummy node is created to make handling edge cases easier. This dummy node points to the head of the list.

2. A pointer, prev, is initialized to point at the dummy node. This pointer keeps track of the last node in the list as we process pairs.

3. A while loop checks that there are at least two nodes available to swap. Inside this loop:

   • We identify the two nodes, first and second, which are to be swapped.
   • The links are then rearranged. The next pointer of the first node is updated to point to the node after the second node, essentially skipping over the second node. The next pointer of the second node points to the first node, completing the swap.
   • The next pointer of the previous node (prev) is updated to point to the second node of the pair, which is now the first after the swap.

4. After processing a pair, prev is moved to point to the first node of the swapped pair, setting it up for the next iteration.

5. Finally, the function returns the new head of the linked list, which is the node following the dummy node.

Testing this function with a sample list can help illustrate the swapping in action:

PythonCopy code

In the above test, we build a simple linked list with nodes 1, 2, 3, and 4. Upon running the swapPairs function, we can observe the expected output. This output should show nodes swapped in pairs resulting in the list: 2 -> 1 -> 4 -> 3 -> None.