> For the complete documentation index, see [llms.txt](https://suki.gitbook.io/91-days-algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/07.swap-nodes-in-pairs.md).
# 24. 两两交换链表中的节点
* [24. 两两交换链表中的节点](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#24-两两交换链表中的节点)
* [题目描述](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#题目描述)
* [方法 1: 迭代](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#方法-1-迭代)
* [图解](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#图解)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#复杂度分析)
* [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#代码javascriptc)
* [方法 2: 递归](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#方法-2-递归)
* [思路](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#思路)
* [复杂度分析](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#复杂度分析-1)
* [代码(JavaScript/C++)](https://suki.gitbook.io/91-days-algorithm/basic/linked-list/pages/-MNWDokvVtTesiVHVUny#代码javascriptc-1)
## 题目描述
```
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```
## 方法 1: 迭代
### 图解
* 要注意指针改变的顺序，不然可能会丢失节点。
* 用一个 dummy 节点来简化操作，不用额外考虑链表头部的情况。
### 复杂度分析
* 时间复杂度：$O(N)$, N 为链表长度。
* 空间复杂度：$O(1)$。
### 代码(JavaScript/C++)
JavaScript Code
```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(null, head);
let prev = dummy;
let cur = prev.next;
while (cur && cur.next) {
// 按照上图，指针更换顺序是这样子的
// prev.next = cur.next
// cur.next = prev.next.next
// prev.next.next = cur
// 也可以先用一个指针把下一个节点存起来
const next = cur.next;
cur.next = next.next;
next.next = cur;
prev.next = next;
prev = cur;
cur = cur.next;
}
return dummy.next;
};
```
C++ Code
```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) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* dummy = new ListNode(0, head);
ListNode* prev = dummy;
ListNode* cur = prev->next;
while (cur != nullptr && cur->next != nullptr) {
ListNode* next = cur->next;
cur->next = next->next;
next->next = cur;
prev->next = next;
prev = cur;
cur = cur->next;
}
return dummy->next;
}
};
```
## 方法 2: 递归
### 思路
“将相邻的链表节点两两交换”，我们可以把链表两两分成若干组，在组内互换节点后再组合起来。
先解决小问题，再把小问题的解组合起来，解决大问题。
**小问题**
只要关注当前递归要解决的问题就行，前后都可以当成是黑匣子。在当前递归中，我们只需要将两个节点互换。
**小问题之间的关系**
* 下一个递归应该返回互换后的第一个节点
* 当前递归应该返回互换后的第一个节点给上一个递归
**递归出口**
* 链表尾部 `head === null`
* 链表最后只剩下一个元素 `head.next === null`
### 复杂度分析
* 时间复杂度：$O(N)$, N 为链表长度。
* 空间复杂度：$O(N)$, N 为链表长度，递归栈的空间。
### 代码(JavaScript/C++)
JavaScript Code
```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) {
// 递归出口
if (!head || !head.next) return head;
// 先保存下一个节点，避免丢失
const next = head.next;
// 下一个递归会返回互换后的第一个节点
// head 是当前组互换后的第二个节点，head.next 指向下一组就好
head.next = swapPairs(next.next);
// 将当前组的两个节点互换
next.next = head;
// 返回互换后的第一个节点
return next;
};
```
C++ Code
```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) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* first = head;
ListNode* second = first->next;
ListNode* head_of_next_group = swapPairs(second->next);
first->next = head_of_next_group;
second->next = first;
return second;
}
};
```
更多题解可以访问：