题目描述

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

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

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

解题思路 & 代码实现

设置一个虚拟头节点帮助操作，否则头节点就要单独处理。

ListNode* dummyHead = new ListNode(0); // 设置虚拟头节点
dummyHead -> next = head; // 让它指向头节点

设置一个指针让其指向虚拟头节点

ListNode* cur = dummyHead;

设置一个指针tmp指向头节点，指针tmp1指向原本链表的第三个节点（即元素3），这一步用于保存位置：

接下来是交换的逻辑：

第一步：

让dummyHead指向元素2

第二步：

让元素2指向元素1

第三步：

让元素1指向元素3

如此三步后就完成了元素1和元素2的互换，随后cur需要向前移动两步，避开已经完成交换的两个元素。

cur = cur -> next -> next;

继续这个过程，直到cur指针的下一个元素为空（cur->next -> nullptr）或者cur指针的下下个元素为空（cur->next->next->nullptr），循环结束。

最后返回真正的头节点即可：

return dummyHead->next;

完整代码如下：

class Solution {
public:
	ListNode* swapPairs(ListNode* head) {
		ListNode* dummyHead = new ListNode(0);
		dummyHead -> next = head;
		ListNode* cur = dummyHead;
		while (cur -> next != nullptr || cur -> next -> next != nullptr) {
			ListNode* tmp = cur -> next;
			ListNode* tmp1 = cur -> next -> next -> next;
			
			cur -> next = cur -> next -> next;  // 第一步
			cur -> next -> next = tmp; 			// 第二步
			cur -> next -> next -> next = tmp1; // 第三步

			cur = cur -> next -> next;
		}
		return dummyHead -> next;
	}
};