一、题目

在这里插入图片描述

二、解法

思路分析：题目要求两两交换节点。在链表当中非常重要就是下一个节点，一旦丢失，这个节点后面的节点也就找不到了。那么我们在需要再交换前后做好保存节点变量的工作，程序当中我们设置了两个临时变量，例如在[1 2 3 4]这个链表当中，第一次交换(交换1 2 节点)，cur指向虚节点，tmp1指向第一个节点（也就是1），tmp2需要指向第三个节点，因此修改指针的过程中会丢失。首先，让cur节点指向第2个节点，第2个节点指向第1个节点，第1个节点指向第3个节点，这样就完成了第一次交换。其次，我们做更新操作，注意第一次交换是三个指针的相对位置(tmp1是cur的下一个节点，tmp2是tmp1的next next节点)，因此下一次循环也循序这个规则。
在这里插入图片描述

程序如下：

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* FakeNode = new ListNode(0, head);ListNode* tmp1;	// 临时变量ListNode* tmp2;	// 临时变量ListNode* cur = FakeNode;	// 头结点的下一个节点while (cur->next != NULL && cur->next->next != NULL) {// 更新tmp1 = cur->next;			// 保存第1个节点，虚节点是第0个节点tmp2 = tmp1->next->next;	// 保存第3个节点//交换cur->next = tmp1->next;		cur->next->next = tmp1;tmp1->next = tmp2;// 更新cur = tmp1;}return FakeNode->next;}
};

复杂度分析：

时间复杂度： $O (n)$ 。
空间复杂度： $O (1)$ 。

三、完整代码

# include <iostream>
using namespace std;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) {ListNode* FakeNode = new ListNode(0, head);ListNode* tmp1;	// 临时变量ListNode* tmp2;	// 临时变量ListNode* cur = FakeNode;	// 头结点的下一个节点while (cur->next != NULL && cur->next->next != NULL) {// 更新tmp1 = cur->next;			// 保存第1个节点，虚节点是第0个节点tmp2 = tmp1->next->next;	// 保存第3个节点//交换cur->next = tmp1->next;		cur->next->next = tmp1;tmp1->next = tmp2;// 更新cur = tmp1;}return FakeNode->next;}
};ListNode* ChainGenerator(int arr[], int len) {ListNode* head = new ListNode(arr[0], NULL);ListNode* p = head;for (int i = 1; i < len; i++) {ListNode* pNewNode = new ListNode(arr[i], NULL);p->next = pNewNode; // 上一个节点指向这个新建立的节点p = pNewNode; // p节点指向这个新的节点}return head;
}void my_print(ListNode* head, string str) {cout << str << endl;ListNode* cur = head;while (cur != NULL) {cout << cur->val << ' ';if (cur->next == NULL) break;cur = cur->next;}cout << endl;
}int main()
{//int arr[] = { 1,2,3,4 };int arr[] = { 1 };int len = sizeof(arr) / sizeof(int);Solution s1;ListNode* head = ChainGenerator(arr, len);my_print(head, "目标链表：");head = s1.swapPairs(head);my_print(head, "翻转后的链表：");system("pause");return 0;
}