Swapping Nodes in Pairs: A Rust Adventure with Linked Lists

Linked list problems are a rite of passage for any programmer. They're fundamental, test your understanding of pointers , and often unveil elegant solutions. Today, we're tackling a classic: Swap Nodes in Pairs.

The problem statement is simple: given a linked list, swap every two adjacent nodes and return its head. The crucial constraint? You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed).

This constraint is where Rust's powerful ownership and borrowing system truly shines (and sometimes frustrates!).

The Problem: Swap Nodes in Pairs

Link to problem : https://leetcode.com/problems/swap-nodes-in-pairs

Example:

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

Let's dive into how we can approach this in Rust.

Approach 1: The Elegant Recursive Solution

Recursion often provides a very clean and intuitive way to solve linked list problems. For "Swap Nodes in Pairs," it's particularly elegant in Rust.

The Logic:

1. Base Case: If the list is empty or has only one node, there's nothing to swap. Return the head as is.
2. Recursive Step:
3. Take the first node.
4. If there's a second node:
5. Recursively call swap_pairs on the rest of the list (starting from what was originally the third node). This will return the correctly swapped tail.
6. Link the original first node to this newly swapped tail.
7. Link the original second node to the original first node.
8. Return the original second node (which is now the head of the swapped pair).

Rust Implementation (Recursive):

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // Use and_then to handle the Option gracefully
        head.and_then(|mut first| { // 'first' is the current head node
            match first.next.take() { // Try to take the next node (becomes 'second')

                // Case 1: We have a 'second' node, so we can swap
                Some(mut second) => {
                    // Recursively swap the rest of the list (starting from third node)
                    // first.next is currently None because we took it, so we can reassign
                    first.next = Self::swap_pairs(second.next.take()); 

                    // The 'first' node now points to the swapped remainder.
                    // Now, make 'second' point to 'first'.
                    second.next = Some(first);

                    // 'second' is now the new head of this swapped pair.
                    Some(second)
                }

                // Case 2: No 'second' node (list is empty or only one node left)
                None => Some(first), // Return the single node as is
            }
        })
    }
}

Why it works in Rust:

• head.and_then(...): This is a clean way to start. If head is None, and_then returns None. If it's Some(node), it unwraps node for us.
• first.next.take(): This is the magic! take() moves the value out of the Box<ListNode> and leaves None in its place. This allows us to reassign first.next later without violating Rust's ownership rules. We effectively extract second to manipulate it.
• Ownership Transfer: The Boxes are moved and reassigned. There are no raw pointers to manage, and Rust ensures everything is dropped correctly.

Approach 2: The Iterative Solution with a Dummy Node

While recursion is elegant, for very long lists, an iterative solution might be preferred to avoid potential stack overflow issues. The iterative approach requires a bit more careful pointer management.

The Logic:

1. Dummy Node: Introduce a dummy head node. This simplifies edge cases where the original head might be swapped. dummy.next will eventually point to our actual new head.
2. curr Pointer: Maintain a curr mutable reference that points to the node before the pair we are about to swap. Initially, curr points to the dummy node.
3. Loop and Swap:
4. Check if there are at least two nodes ahead of curr to swap.
5. Identify first and second nodes of the pair.
6. Perform the actual pointer reassignments to swap first and second.
7. Advance curr two steps forward to prepare for the next pair.

Rust Implementation (Iterative):

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        // 1. Create a dummy node to simplify head manipulation
        // It points to the original head.
        let mut dummy = Box::new(ListNode { val: 0, next: head });

        // 'curr' is a mutable reference to the node *before* the pair we want to swap.
        // Initially, it's the dummy node.
        let mut curr = &mut dummy;

        // Loop as long as there are at least two nodes ahead to swap
        while curr.next.is_some() && curr.next.as_ref().unwrap().next.is_some() {
            // 2. Take the 'first' node out of 'curr.next'
            // curr.next becomes None temporarily
            let mut first = curr.next.take().unwrap();

            // 3. Take the 'second' node out of 'first.next'
            // first.next becomes None temporarily
            let mut second = first.next.take().unwrap();

            // --- Perform the actual swapping of pointers ---

            // 4. 'first' node should now point to what 'second' *used* to point to
            first.next = second.next.take(); 

            // 5. 'second' node should now point to 'first'
            second.next = Some(first);

            // 6. The node before the pair ('curr') should now point to 'second'
            curr.next = Some(second);

            // --- Move 'curr' forward two positions for the next iteration ---
            // 'curr' now points to the original 'second' node (which is now the head of the swapped pair)
            // Then move again to point to the original 'first' node (which is now the second in the pair)
            // This sets 'curr' *before* the next pair.
            curr = curr.next.as_mut().unwrap().next.as_mut().unwrap();
        }

        // The actual head of the swapped list is what dummy.next points to
        dummy.next
    }
}

Challenges and Rust-specific solutions:

• Borrow Checker Dance: The iterative solution involves more take(), unwrap(), and mutable references (&mut) because we need to temporarily unhook nodes to re-link them. The compiler ensures we don't create invalid states.
• curr.next.as_mut().unwrap().next.as_mut().unwrap(): This looks a bit clunky, but it's how we navigate through Option<Box<ListNode>> chains with mutable references. Each as_mut().unwrap() gives us a mutable reference to the Box<ListNode> inside the Option, allowing us to access its next field.

Conclusion

Both recursive and iterative solutions effectively solve the "Swap Nodes in Pairs" problem while adhering to the constraint of not modifying node values.

• The recursive solution offers remarkable clarity and conciseness, especially suitable for Rust's functional approach to Option and Box.
• The iterative solution provides more explicit control over memory and avoids recursion depth limits, though it requires a deeper understanding of mutable borrowing and take() operations in Rust.

Which approach do you find more intuitive? Let me know in the comments!

---