Swap pairs in place

We’ll solve this through a recursive solution and iteratively. Before we get there, however, let’s build some intuition around what we need to do.

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.)

For example, take the linked list: 1 -> 2 -> 3 -> 4, we need to transform it into 2 -> 1 -> 4 -> 3. Let’s break this down into a really simple case where we only have 2 nodes.

1 -> 2 needs to transform into 2 -> 1.

We’re given the input, a list/array with the singly linked list and a single function that accepts one argument, the head of the nodes. It’s our job to return the head of the list.

I’ll be writing this in Rust, but it is easily translatable to other languages. The structure of a ListNode looks like this:

	
		
			
			
		
	

	#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

We have access to the val and the next pointer as an Option<Box<T>>. In rust, this means we can check for None (in Python, we would check for None, TS/JS we’d check for null, and so on).

We’re given the base structure of a solution:

	
		
			
			
		
	

	impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    }
}

Basecase

If we’re handed a node that is None, it’s our job just to return the head node. If we’re not handled a None node, we’ll have to update the pointers. Using rust, we can create a simple match statement:

	
		
			
			
		
	

	impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => head,
            Some(first_node) => {
                // Do something here
            }
        }
    }
}

We’ll need to find a way to see what the next node is (if it exists) and connect the next node to the current one. If at any point, the head node or the head.next nodes are None, we just have to return the head. We can’t update a node without a next:

	
		
			
			
		
	

	impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => head,
            Some(first_node) => {
                match first_node.next {
                    None => Some(first_node),
                    Some(next_node) => {
                        // Update pointers
                    }
                }
            }
        }
    }
}

If we’ve fallen into the case where the next node is not None, we’re in the spot where we have to handle some swapping.

In the recursive world, we’ll have to call the Solution::swap_pairs() function again to find the next node as we don’t yet know it in the iteration we’re in.

	
		
			
			
		
	

	impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => head,
            Some(first_node) => {
                match first_node.next {
                    None => Some(first_node),
                    Some(next_node) => {
                        // Update pointers
                        // Get the next linked nodes
                        first_node.next = Self::swap_pairs(next_node.next);
                        // Take the next node and link it's `next` to
                        // the node we're currently on:
                        next_node.next = Some(first_node);
                        Some(next_node)
                    }
                }
            }
        }
    }
}

If you’re experienced in rust, you’ll notice a big problem. We can’t update the node if it’s not mutable. We can easily update them by declaring any nodes we’re updating as mutable.

	
		
			
			
		
	

	impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => head,
            // Update `first_node` as mutable
            Some(mut first_node) => {
                match first_node.next {
                    None => Some(first_node),
                    // Update `next_node` as mutable
                    Some(mut next_node) => {
                        // Update pointers
                        // Get the next linked nodes
                        first_node.next = Self::swap_pairs(next_node.next);
                        // Take the next node and link it's `next` to
                        // the node we're currently on:
                        next_node.next = Some(first_node);
                        Some(next_node)
                    }
                }
            }
        }
    }
}

Challenges

[] Implement this in Python
[] Implement this in JavaScript/TypeScript