leetcode24. 两两交换链表中的节点

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]

思路：
1、创建哑结点 dummy，令 dummy.next = head，令cur 表示当前到达的节点，初始时 cur = dummy。每次需要交换cur后面的两个节点。
2、如果 cur的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。否则，获得cur后面的两个节点cur.next 和cur.next.next，通过更新节点的指针关系实现两两交换节点。具体而言，交换之前的节点关系是 cur-> cur.next -> cur.next.next，交换之后的节点关系要变成 cur-> cur.next.netxt-> cur.next，因此需要进行如下操作。
cur.next = cur.next.next
cur.next .next = cur.next.netxt.next
cur.next.netxt.next = cur.next
3、完成上述操作之后，节点关系即变成 cur-> cur.next.netxt-> cur.next。再令cur = cur.next，对链表中的其余节点进行两两交换，直到全部节点都被两两交换。
两两交换链表中的节点之后，新的链表的头节点是 dummy.next，返回新的链表的头节点即可。

#include <iostream>
#include <algorithm>
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) {}
};
ListNode* swapPairs(ListNode* head) {if (head == nullptr)return head;ListNode* dummy = new ListNode(-1,head);//前驱节点头ListNode* cur = dummy;//前驱节点的假头（需要移动）while (head != nullptr){if (head->next == nullptr)break;//链表个数为奇数时 最后一个不执行操作ListNode* next = head->next;//保存当前节点的后驱节点head->next = head->next->next;//断链 修改当前节点的后驱节点cur->next = next;//修改当前节点的前驱节点next->next = head;//修改后驱节点的指向cur = head;//前驱节点移动head = head->next;//当前节点移动}return dummy->next;//返回创建的前驱节点头的下一个节点
}
int main() {ListNode node1, node2, node3, node4;node1.val = 1;node1.next = &node2;node2.val = 2;node2.next = &node3;node3.val = 3;node3.next = &node4;node4.val = 4;node4.next = nullptr;ListNode* res = swapPairs(&node1);while (res != nullptr){cout << res->val << " ";res = res->next;}cout << endl;return 0;
}