Follow

# .css-ecb9sr{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;width:16rem;}  Follow # 24. Swap Nodes in Pairs

## How to swap two nodes in a linked-list

Nhut Nguyen
·Dec 5, 2022·

### Problem statement

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]
``````

#### Example 2

``````Input: head = []
Output: []
``````

#### Example 3

``````Input: head = 
Output: 
``````

#### Constraints

• The number of nodes in the list is in the range `[0, 100]`.

• `0 <= Node.val <= 100`.

### Solution

Draw a picture of the swapping to identify the correct order of the update. Denote `(cur, next)` the pair of nodes you want to swap and `prev` be the previous node that links to `cur`. Here are the steps you need to perform for the swapping.

1. Update the links between nodes.

2. Go to the next pair.

#### Code

``````#include <iostream>
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) {}
};
}
ListNode* preNode = nullptr;
while (curNode != nullptr && nextNode != nullptr) {
curNode->next = nextNode->next;
nextNode->next = curNode;
if (preNode) {
preNode->next = nextNode;
}
preNode = curNode;
curNode = curNode->next;
if (curNode) {
nextNode = curNode->next;
}
}
}
std::cout << "[";
while (node != nullptr) {
std::cout << node->val << ",";
node = node->next;
}
std::cout << "]" << std::endl;
}
int main() {
ListNode four(4);
ListNode three(3, &four);
ListNode two(2, &three);
ListNode one(1, &two);
print(swapPairs(&one));
ListNode five(5);
print(swapPairs(nullptr));
print(swapPairs(&five));
}
``````
``````Output:
[2,1,4,3,]
[]
[5,]
``````

#### Complexity

• Runtime: `O(N)`, where `N` is the number of nodes.

• Extra space: `O(1)`.

### References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.