This is a classic linked list problem that requires understanding how to manipulate pointers and traverse linked lists. The key insight is understanding pointer manipulation, recursion, and iterative approaches with dummy nodes.

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Examples

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints

  • The number of nodes in the list is in the range [0, 100]
  • 0 <= Node.val <= 100

Thinking Process

There are two main approaches to solve this problem:

  1. Recursive Approach: Use recursion to swap pairs and handle the rest of the list
  2. Iterative Approach: Use a dummy node and pointers to traverse and swap pairs
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

Recursive Approach

Time Complexity: O(n) - We visit each node once
Space Complexity: O(n) - Due to recursion stack

The recursive approach works by:

  1. Base case: If we have 0 or 1 nodes, return the head
  2. Swap the first two nodes
  3. Recursively call the function on the rest of the list
  4. Connect the swapped pair with the result from recursion 
    /**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() { this.val = 0; this.next = null; }
 *     ListNode(int x) { this.val = x; this.next = null; }
 *     ListNode(int x, ListNode next) { this.val = x; this.next = next; }
 * }
 */
class Solution {
 public ListNode swapPairs(ListNode head) {
     if ((head == null) || (head.next == null)) return head;
     ListNode first = head;
     ListNode second = head.next;
     first.next = swapPairs(second.next);
     second.next = first;
     return second;
 }
}

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: There are two main approaches to solve this problem:

How the code works:

  1. Recursive Approach: Use recursion to swap pairs and handle the rest of the list
  2. Iterative Approach: Use a dummy node and pointers to traverse and swap pairs

Walkthrough — input head = [1,2,3,4], expected output [2,1,4,3]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  • Forgetting to update the pre pointer in iterative approach
  • Not handling the case where there’s an odd number of nodes
  • Incorrectly connecting pointers during the swap operation

References

Key Takeaways

  1. Dummy Node: The iterative approach uses a dummy node to simplify edge cases
  2. Pointer Manipulation: Understanding how to update multiple pointers correctly
  3. Recursion vs Iteration: Recursive is more elegant but uses O(n) space; iterative uses O(1) space
  4. Base Cases: Always handle empty list and single node cases