【算法】链表：24.两两交换链表中的节点
目录
1、题目链接
2、题目介绍
3、解法
4、代码
1、题目链接
24. 两两交换链表中的节点 - 力扣（LeetCode）
2、题目介绍
3、解法
- 引入伪头节点：
- 为了处理头节点可能被交换的情况，我们引入一个伪头节点（dummy node），它的
next指针指向原链表的头节点。这样做可以简化边界条件的处理，因为头节点也可能需要被交换。- 初始化指针：
prevPair：记录当前处理的节点对之前的那个节点，初始化为伪头节点。first：当前处理的节点对中的第一个节点，初始化为链表的头节点。second：当前处理的节点对中的第二个节点，初始化为头节点的下一个节点（如果存在）。- 遍历链表：
- 使用一个
while循环遍历链表，条件是first和second都不为空。这表示还有节点对需要处理。- 交换节点：
- 在每次循环中，首先记录下一对节点的起始位置（
nextPairStart），即当前second节点的下一个节点。- 然后，交换
first和second节点的位置。这通过调整指针来完成，而不需要移动节点本身。- 更新
prevPair->next，使其指向新的第一个节点（原来的second节点）。- 更新
second->next，使其指向原来的first节点。- 更新
first->next，使其指向nextPairStart，即下一对节点的起始位置。- 更新指针：
- 更新
prevPair为当前处理的节点对中的第一个节点（经过交换后可能变成了第二个节点，但在这里我们总是更新为逻辑上的“第一个”，即当前对的最前端）。- 更新
first为下一对节点的第一个节点（nextPairStart）。- 如果
first不为空，则更新second为first->next；否则，将second设置为nullptr（虽然这在循环结束时自动成立，但显式设置可以提高代码清晰度）。- 返回结果：
- 循环结束后，返回伪头节点的
next指针，它现在指向交换后的链表的头节点。关键点：
- 使用伪头节点简化边界条件处理。
- 通过调整指针来交换节点，而不是移动节点本身。
- 正确地更新所有相关的指针，以确保链表结构的完整性。
4、代码
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head; // 伪头节点
ListNode* prevPair = dummy; // 记录每一对节点的前一个节点
ListNode* first = head; // 当前处理的节点对中的第一个节点
ListNode* second = head ? head->next : nullptr; // 当前处理的节点对中的第二个节点
while (first && second) {
// 记录下一对节点的第一个一个节点
ListNode* nextPairStart = second->next;
// 交换节点
prevPair->next = second;
second->next = first;
first->next = nextPairStart;
// 更新 prevPair 和节点对
prevPair = first;
first = nextPairStart;
if (first) {
second = first->next;
}
else {
second = nullptr;
}
}
return dummy->next;
}
};