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:

1class ListNode:
2    def __init__(self, value=0, next=None):
3        self.value = value
4        self.next = next
5
6def swapPairs(head):
7    # Create a dummy node to simplify swaps.
8    dummy = ListNode(0)
9    dummy.next = head
10    prev = dummy
11
12    # Loop through the list in pairs
13    while prev.next and prev.next.next:
14        # Identify the two nodes to swap
15        first = prev.next
16        second = first.next
17
18        # Perform the swapping
19        first.next = second.next
20        second.next = first
21        prev.next = second
22
23        # Move to the next pair
24        prev = first
25
26    # Return the new head of the swapped list
27    return dummy.next

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:

1def printList(head):
2    while head:
3        print(head.value, end=" -> ")
4        head = head.next
5    print("None")
6
7# Create a sample linked list: 1 -> 2 -> 3 -> 4 -> None
8head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
9
10print("Original list:")
11printList(head)
12
13swapped_head = swapPairs(head)
14
15print("Swapped list:")
16printList(swapped_head)

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.