【算法--链表题5】24.两两交换链表中的节点--通俗讲解

一、题目是啥？一句话说清

给定一个链表，交换每两个相邻的节点（不能只改值，要实际交换节点），并返回交换后的链表。

示例：

• 输入：1 → 2 → 3 → 4
• 输出：2 → 1 → 4 → 3

二、解题核心

使用虚拟头节点简化操作，然后遍历链表，每次交换两个相邻节点，并正确更新指针以保持链表连接。 这就像排队时，每两个人互换位置，但要注意换完后重新连接好队伍，不能断开。

三、关键在哪里？（3个核心点）

想理解并解决这道题，必须抓住以下三个关键点：

1. 虚拟头节点（Dummy Node）的使用

• 是什么：在原始链表前添加一个不存储实际数据的节点。
• 为什么重要：交换后头节点可能改变（例如原来头节点是1，交换后变成2），使用虚拟头节点可以避免单独处理头节点变化的特殊情况。

2. 指针操作的顺序

• 是什么：交换节点时，需要调整多个指针的指向顺序。
• 为什么重要：如果指针操作顺序错误，容易导致链表断开或形成环。正确的顺序是：先记录要交换的两个节点，然后让前驱节点指向第二个节点，再让第一个节点指向第二个节点的下一个，最后让第二个节点指向第一个节点。

3. 循环条件的控制

• 是什么：循环需要继续的条件是当前节点后面至少还有两个节点可以交换。
• 为什么重要：如果链表长度是奇数，最后一个节点不需要交换；如果链表为空或只有一个节点，则不需要任何操作。

四、看图理解流程（通俗理解版本）

让我们用链表 1 → 2 → 3 → 4 的例子来可视化过程：

1. 初始化：

   • 创建虚拟头节点 dummy，其 next 指向头节点 1。
   • 设置当前指针 curr 指向 dummy。
   • 初始状态：dummy → 1 → 2 → 3 → 4

2. 第一轮交换（交换1和2）：

   • 记录第一个要交换的节点 first = curr.next (1)
   • 记录第二个要交换的节点 second = curr.next.next (2)
   • 执行交换：
     • curr.next = second（dummy现在指向2）
     • first.next = second.next（1现在指向3）
     • second.next = first（2现在指向1）
   • 交换后链表：dummy → 2 → 1 → 3 → 4
   • 移动 curr 到 first（即交换后的第一个节点1），因为下一轮要交换1后面的节点

3. 第二轮交换（交换3和4）：

   • 现在 curr 指向节点1
   • 记录 first = curr.next (3)
   • 记录 second = curr.next.next (4)
   • 执行交换：
     • curr.next = second（1现在指向4）
     • first.next = second.next（3现在指向null）
     • second.next = first（4现在指向3）
   • 交换后链表：dummy → 2 → 1 → 4 → 3
   • 移动 curr 到 first（即节点3）

4. 结束：

   • curr 后面没有两个节点了，循环结束。
   • 返回 dummy.next，即新头节点2。

五、C++ 代码实现（附详细注释）