# 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;
}
};
```
更多题解可以访问：
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://suki.gitbook.io/91-days-algorithm/basic/linked-list/07.swap-nodes-in-pairs.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.