Back to leetcode

# 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

© 2024 Ari Lerner. All rights reserved.