# Swap Nodes in Pairs
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/swap-nodes-in-pairs)
Canonical: https://scaleengineer.com/dsa/problems/swap-nodes-in-pairs
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Linked List
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber)
---
## Problem
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.)

**Example 1:**

**Input:** head = \[1,2,3,4\]

**Output:** \[2,1,4,3\]

**Explanation:**

![](https://assets.glich.co/dsa/swap-nodes-in-pairs/image0.jpg)

**Example 2:**

**Input:** head = \[\]

**Output:** \[\]

**Example 3:**

**Input:** head = \[1\]

**Output:** \[1\]

**Example 4:**

**Input:** head = \[1,2,3\]

**Output:** \[2,1,3\]

**Constraints:**

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

# Approaches
## Recursive Approach
This approach solves the problem by defining a function that swaps the first two nodes of a list and then recursively calls itself on the rest of the list. The base case for the recursion is a list with zero or one node, which is returned as is.
**Time:** O(N) · **Space:** O(N)
**Pros:** The code is concise and closely follows the recursive structure of the problem, which can make it easier to understand.; It naturally handles the head of the list without needing a special dummy node.
**Cons:** The space complexity is O(N) due to the recursion call stack, which is less efficient than an iterative solution.; For extremely long linked lists, this approach could lead to a `StackOverflowError` (though not an issue with the problem's constraints).
### Explanation
The recursive solution elegantly mirrors the definition of the problem. The main idea is to handle the first pair of nodes and then delegate the swapping of the remaining pairs to a recursive call. 

Let's consider the list `1 -> 2 -> 3 -> 4`. The function `swapPairs` is called on the head (node 1).
1. It identifies the first pair (1, 2).
2. It knows that after swapping, node 1's `next` pointer should point to the result of swapping the rest of the list, which is `3 -> 4`.
3. It makes a recursive call `swapPairs(3)`. This call will return the head of the swapped sublist, which is `4 -> 3`.
4. Now, it can complete the swap of the first pair. It sets `1.next` to `4` and `2.next` to `1`.
5. Finally, it returns `2` as the new head of the entire list.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // Base case: if the list has 0 or 1 node, no swaps needed.
        if (head == null || head.next == null) {
            return head;
        }

        // Nodes to be swapped
        ListNode firstNode = head;
        ListNode secondNode = head.next;

        // Recursively call for the list starting from the third node.
        // This will be the new next for the first node after swapping.
        firstNode.next = swapPairs(secondNode.next);

        // Swap the first two nodes by changing pointers
        secondNode.next = firstNode;

        // secondNode is the new head of the swapped pair
        return secondNode;
    }
}
```
### Algorithm
- Check for the base case: if the list is empty (`head == null`) or has only one node (`head.next == null`), return the `head` as no swap is possible.
- Identify the first two nodes to be swapped: `firstNode = head` and `secondNode = head.next`.
- The rest of the list, starting from `secondNode.next`, needs to be processed recursively. Call `swapPairs(secondNode.next)`.
- Link the `firstNode` to the result of the recursive call. This means `firstNode.next` will point to the head of the swapped sublist.
- Perform the swap for the current pair: `secondNode.next` should point to `firstNode`.
- Return `secondNode`, as it is the new head of this swapped pair.

## Iterative Approach with Dummy Node
This approach iterates through the linked list, swapping nodes in pairs. A dummy node is used to simplify the logic, especially for swapping the first pair of nodes, as it provides a constant reference to the node preceding the pair being swapped.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal space complexity of O(1), as it only uses a constant amount of extra space.; Avoids potential stack overflow issues, making it more robust and suitable for very large inputs.
**Cons:** The pointer manipulation can be slightly more complex to write and debug compared to the recursive version.; Requires a dummy node to handle the edge case of the head gracefully.
### Explanation
To achieve optimal O(1) space complexity, we can solve the problem iteratively. This avoids the overhead of the recursion stack. The key is to carefully manage the pointers to relink the nodes correctly after each swap.

We use a `dummy` node that points to the original `head`. This `dummy` node's `next` pointer will eventually point to the new head of the modified list. A `prevNode` pointer tracks the node just before the pair we are about to swap, allowing us to correctly link the previous part of the list to the newly swapped pair.

For a list `1 -> 2 -> 3 -> 4`, the process is:
- Initial state: `dummy -> 1 -> 2 -> 3 -> 4`. `prevNode` is `dummy`.
- **Iteration 1:** Swap 1 and 2. `prevNode` (dummy) now points to 2. The list becomes `dummy -> 2 -> 1 -> 3 -> 4`. Update `prevNode` to 1 for the next swap.
- **Iteration 2:** Swap 3 and 4. `prevNode` (node 1) now points to 4. The list becomes `dummy -> 2 -> 1 -> 4 -> 3`. Update `prevNode` to 3.
- The loop terminates as there are no more pairs.
- The final list is returned by `dummy.next`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // A dummy node acts as the previous node for the head.
        // This simplifies the logic for swapping the first pair.
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prevNode = dummy;

        while (head != null && head.next != null) {
            // Nodes to be swapped
            ListNode firstNode = head;
            ListNode secondNode = head.next;

            // Swapping
            prevNode.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;

            // Re-initializing the prevNode and head for the next iteration
            prevNode = firstNode;
            head = firstNode.next; // a.k.a. the start of the next pair
        }

        return dummy.next;
    }
}
```
### Algorithm
- Create a `dummy` node and set its `next` pointer to the `head` of the list. This simplifies handling the list's head.
- Initialize a `prevNode` pointer to the `dummy` node.
- Iterate through the list as long as the current node and its next node are not null.
- In each iteration, identify the pair to be swapped: `firstNode` (current) and `secondNode` (current.next).
- Rearrange the pointers to perform the swap:
  - `prevNode.next` points to `secondNode`.
  - `firstNode.next` points to `secondNode.next`.
  - `secondNode.next` points to `firstNode`.
- Update `prevNode` to `firstNode` (which is now the second node in the swapped pair) to prepare for the next iteration.
- Move the current pointer to the start of the next pair.
- After the loop finishes, return `dummy.next`, which now points to the new head of the modified list.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode SwapPairs ( ListNode head ) { if ( head is null || head . next is null ) { return head ; } ListNode t = SwapPairs ( head . next . next ); ListNode p = head . next ; p . next = head ; head . next = t ; return p ; } }
```

### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode swapPairs ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); ListNode pre = dummy ; ListNode cur = head ; while ( cur != null && cur . next != null ) { ListNode t = cur . next ; cur . next = t . next ; t . next = cur ; pre . next = t ; pre = cur ; cur = cur . next ; } return dummy . next ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var swapPairs =
  function (head) {
    const dummy = new ListNode(0, head);
    let [pre, cur] = [dummy, head];
    while (cur && cur.next) {
      const t = cur.next;
      cur.next = t.next;
      t.next = cur;
      pre.next = t;
      [pre, cur] = [cur, cur.next];
    }
    return dummy.next;
  };

```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * swapPairs ( ListNode * head ) { ListNode * dummy = new ListNode ( 0 , head ); ListNode * pre = dummy ; ListNode * cur = head ; while ( cur && cur -> next ) { ListNode * t = cur -> next ; cur -> next = t -> next ; t -> next = cur ; pre -> next = t ; pre = cur ; cur = cur -> next ; } return dummy -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def swapPairs ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode ( next = head ) pre , cur = dummy , head while cur and cur . next : t = cur . next cur . next = t . next t . next = cur pre . next = t pre , cur = cur , cur . next return dummy . next
```