Problem Description

You are given a singly linked list. Your task is to swap every two adjacent nodes in the list and return the head of the modified list.

The key constraint is that you cannot modify the values inside the nodes - you can only change the node connections themselves. This means you need to rearrange the pointers between nodes rather than swapping the data they contain.

For example:

• If the input list is 1 -> 2 -> 3 -> 4, the output should be 2 -> 1 -> 4 -> 3
• If the input list is 1 -> 2 -> 3, the output should be 2 -> 1 -> 3
• If the input list is empty or has only one node, return it as is

The solution uses a recursive approach where:

1. The base case handles when there are no nodes or only one node left (nothing to swap)
2. For each pair of nodes, we:
   • Recursively process the rest of the list starting from the third node
   • Save the second node as p
   • Make p point to the first node
   • Make the first node point to the result of the recursive call
   • Return p as the new head of this portion

This effectively swaps each pair of nodes throughout the entire linked list.

Intuition

When we need to swap pairs of nodes in a linked list, we can think of the problem as repeatedly performing the same operation: taking two nodes and swapping them. This repetitive nature suggests that recursion might be a clean solution.

Let's think about what happens when we swap just one pair of nodes. If we have A -> B -> rest, we want to transform it into B -> A -> rest. To do this, we need to:

• Make B point to A
• Make A point to whatever comes after B

But here's the key insight: "whatever comes after B" might also need to be swapped! If the rest of the list is C -> D -> E, then after swapping, it should become D -> C -> E. This means we need to process the rest of the list first before we can properly connect our swapped pair.

This naturally leads to a recursive approach:

1. First, recursively swap all pairs starting from the third node onwards
2. Then swap the current pair and connect it to the already-swapped rest of the list

The beauty of this approach is that each recursive call only needs to worry about swapping one pair and trusting that the recursive call will handle the rest correctly. When we reach the end of the list (no nodes or just one node left), we've hit our base case where no swapping is needed.

By working backwards from the end of the list to the beginning, each pair gets properly connected to an already-processed remainder, ensuring all the pointers are correctly updated without needing to track multiple pointers or use dummy nodes.

Learn more about Recursion and Linked List patterns.

Solution Approach

The recursive solution implements the swapping of node pairs by processing the linked list from the end towards the beginning.

Let's walk through the implementation step by step:

Base Case:

if head is None or head.next is None:
    return head

This handles two scenarios:

• Empty list (head is None)
• Single node (head.next is None)

In both cases, no swapping is possible, so we return the head as-is.

Recursive Case:

1. Process the rest of the list first:

   t = self.swapPairs(head.next.next)

   We recursively call swapPairs on the sublist starting from the third node (head.next.next). The variable t will hold the head of the already-swapped remainder of the list.

2. Perform the swap for current pair:

   p = head.next
   p.next = head
   head.next = t

   • Save the second node in variable p (this will become the new head of this pair)
   • Make p.next point to head (reversing the link between first and second nodes)
   • Make head.next point to t (connecting the first node to the swapped remainder)

3. Return the new head:

   return p

   The second node of the original pair is now the first node, so we return p.

Example Walkthrough:

For list 1 -> 2 -> 3 -> 4:

• First call: swapPairs(1) calls swapPairs(3)
• Second call: swapPairs(3) calls swapPairs(None)
• Third call: swapPairs(None) returns None
• Back to second call: Swaps 3 and 4, returns node 4 (which points to 3)
• Back to first call: Swaps 1 and 2, connects 1 to node 4, returns node 2

Final result: 2 -> 1 -> 4 -> 3

The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(n) due to the recursion stack depth.

Example Walkthrough

Let's trace through the algorithm with a simple 4-node list: 1 -> 2 -> 3 -> 4

Initial Setup:

head points to node 1
1 -> 2 -> 3 -> 4 -> None

Call Stack Progression:

Call 1: swapPairs(node 1)

• head = node 1, head.next = node 2 (not null, so continue)
• Before swapping this pair, recursively process from node 3: t = swapPairs(node 3)

Call 2: swapPairs(node 3)

• head = node 3, head.next = node 4 (not null, so continue)
• Before swapping this pair, recursively process from node 5 (None): t = swapPairs(None)

Call 3: swapPairs(None)

• head = None triggers base case
• Returns None

Back to Call 2: Now swap nodes 3 and 4

• t = None (returned from Call 3)
• p = node 4 (save the second node)
• p.next = node 3 (node 4 now points to node 3)
• node3.next = None (node 3 points to the processed remainder)
• Returns node 4
• Current state: 4 -> 3 -> None

Back to Call 1: Now swap nodes 1 and 2

• t = node 4 (returned from Call 2, this is the head of "4 -> 3")
• p = node 2 (save the second node)
• p.next = node 1 (node 2 now points to node 1)
• node1.next = node 4 (node 1 points to the processed remainder)
• Returns node 2
• Final state: 2 -> 1 -> 4 -> 3 -> None

Key Observations:

• The recursion processes pairs from the end of the list backwards
• Each recursive call handles exactly one pair swap
• The returned value from each call becomes the new head of that portion
• Connections are made after the recursive call returns, ensuring proper linking

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm recursively processes each pair of nodes in the linked list. Since the recursive function is called once for every pair of nodes (moving forward by 2 nodes each time with head.next.next), it will make approximately n/2 recursive calls where n is the total number of nodes. Each recursive call performs a constant amount of work O(1) - just rearranging pointers. Therefore, the total time complexity is O(n/2) * O(1) = O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack. Since the function calls itself recursively until it reaches the end of the list (base case), the maximum depth of the recursion stack will be n/2 (as we process pairs of nodes). Each recursive call uses O(1) space for its local variables (t and p). Therefore, the total space complexity is O(n/2) = O(n) due to the recursive call stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Losing Track of Node References During Swapping

One of the most common mistakes when swapping nodes is accidentally losing references to nodes, which can break the linked list or create incorrect connections.

Pitfall Example:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    # WRONG: Modifying head.next before saving necessary references
    head.next = self.swapPairs(head.next.next)  # Lost reference to second node!
    # Now we can't access the original second node to complete the swap

Solution: Always save the nodes you need before modifying any next pointers:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    # Save the second node FIRST
    second = head.next
    # Then proceed with recursive call and swapping
    head.next = self.swapPairs(second.next)
    second.next = head
    return second

2. Incorrect Order of Pointer Reassignments

The order in which you update the next pointers matters significantly. Doing them in the wrong order can create cycles or break connections.

Pitfall Example:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    second = head.next
    # WRONG ORDER: This creates a cycle!
    second.next = head  # Now second -> head
    head.next = second.next  # This makes head.next point to itself!
  
    return second

Solution: Process the rest of the list first, then update pointers in the correct order:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    # First, process the rest of the list
    remaining = self.swapPairs(head.next.next)
  
    # Then update pointers in correct order
    second = head.next
    second.next = head
    head.next = remaining  # Connect to the already-processed remainder
  
    return second

3. Forgetting Edge Cases in Base Condition

Another common mistake is having an incomplete base case that doesn't handle all scenarios where swapping shouldn't occur.

Pitfall Example:

def swapPairs(self, head):
    # WRONG: Only checking for empty list
    if head is None:
        return head
  
    # This will cause an error when head.next is None
    remaining = self.swapPairs(head.next.next)  # AttributeError!

Solution: Always check both conditions - empty list AND single node:

def swapPairs(self, head):
    # Correct: Check for both empty list and single node
    if head is None or head.next is None:
        return head
  
    # Now safe to access head.next.next
    remaining = self.swapPairs(head.next.next)

4. Attempting to Modify Values Instead of Pointers

While not directly a bug in the recursive approach, developers sometimes try to "simplify" by swapping values instead of nodes, which violates the problem constraints.

Pitfall Example:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    # WRONG: This violates the constraint of not modifying node values
    head.val, head.next.val = head.next.val, head.val
    self.swapPairs(head.next.next)
    return head

Solution: Stick to pointer manipulation only:

def swapPairs(self, head):
    if head is None or head.next is None:
        return head
  
    # Correct: Only manipulate pointers, not values
    remaining = self.swapPairs(head.next.next)
    second = head.next
    second.next = head
    head.next = remaining
    return second