题目描述
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
提示：
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
解题思路
通过阅读题目，发现该题目有重复的子问题，那就是交换2个节点再链接到剩下的部分节点的链表。
然后再把后边的链表按照这种方式继续链接。
但是为了更好的链接，我们先把后面的节点进行两两的交换。交换的时候用头插的方法。
代码
递归——从前往后
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr||head->next==nullptr) return head; ListNode* phead=new ListNode;//设置头节点 ListNode* next=head->next;//保存下一个节点的地址 ListNode* t=next->next;//下一对需要交换的地址 phead->next=next; next->next=head; delete phead; head->next=swapPairs(t); return next; } };
递归——从后往前（更简洁）
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr||head->next==nullptr) return head; ListNode* newhead=swapPairs(head->next->next); //交换的逻辑 ListNode* next=head->next; next->next=head; head->next=newhead; return next; } };
循环的方式
class Solution { public: ListNode* swapPairs(ListNode* head) { if(head==nullptr||head->next==nullptr) return head; ListNode* phead=new ListNode; ListNode* tail=phead; ListNode* next,*t; while(head) { next=head->next; if(next==nullptr) { tail->next=head; break; } if(next!=nullptr) t=next->next; tail->next=next; next->next=head; //注意这里 head->next=nullptr; tail=head; head=t; } return phead->next; } };
