给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:

输入:head = [1,2,3,4] 输出:[2,1,4,3]
示例 2:
输入:head = [] 输出:[]
示例 3:
输入:head = [1] 输出:[1]
提示:
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
初始代码
/**
* 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) {
}
};
解决思路
递归实现
先观察题目。发现“两两交换”这个操作对于一个有n个元素(n>1)的链表来说,是重复操作–即可以使用递归处理的。
类比于斐波那契数列,我们先看看n≤1的情况,发现函数返回值就是head。那么可以写出:
ListNode* swapPairs(ListNode* head) {
if(head==NULL||head->next==NULL) //n=0或n=1
return head;
}
然后在看看n≥2的情况。链表中的第二个节点与第一个节点交换后,第二个节点变成了新的头节点;原本的头节点变成了第二个节点,并且连接着链表后续的内容。
根据递归的相关知识(把递归过程看作一个栈),假设现在链表为[1,2,3,4]。那么我们可以得到代码:
- ListNode* tmp =head->next;
- 链表中的每两个节点,取第一个节点为head,第二个节点为tmp。
- 如果链表中元素个数为奇数,tmp=NULL。
- head->next=swapPairs(tmp->next);
- 每次递归的过程都被存入了栈中,直到传入的节点为空或传入节点的下一个节点为空。
- 因为是每两个节点取一次head和tmp,所以当tmp=NULL(链表中元素个数为奇数),或tmp->next=NULL(tmp是链表最后一个元素)时,停止递归的“递”操作。
- “归”操作就是把栈顶元素弹出,把它的值传给新的栈顶元素。
- 该操作就是将head的next指针指向tmp的下一个节点。
- tmp->next=head;
- 该操作将tmp的next指针指向head节点。
- return tmp;
- 最后的tmp便是新的head节点。
把tmp->next=…理解为“将tmp节点的next指针指向某个节点”,而不是“tmp节点的next指针等于某个节点”就很好明白了,以下是流程图和完整代码
流程图

完整代码
/**
* 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==NULL||head->next==NULL)
return head;
ListNode* tmp=head->next;
head->next=swapPairs(tmp->next);
tmp->next=head;
return tmp;
}
};