Hot 100 --- 两两交换链表中的节点

本文概览：本文以LeetCode经典题目"两两交换链表中的节点"为例，重点讲解如何通过哑节点解决新头节点问题，如何用 prev、first、second 三个指针完成两两交换，以及如何判断循环结束条件

---

一、题目

二、题目分析

给定一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点

目标：交换节点本身，而不是只交换节点值

核心难点：链表节点交换本质上是指针重连，容易断链或者丢失后续节点

这道题主要有三个问题需要解决：

1. 怎么返回新的头节点？
2. 怎么交换两个相邻节点？
3. 循环什么时候结束？

思路概览

Java实现代码如下

public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 创建哑节点
    ListNode dummy = new ListNode(0, head);
    // 初始化前指针
    ListNode prev = dummy;
    // 交换后面两个节点
    ListNode first;
    ListNode second;
    // 交换节点
    while (prev.next != null && prev.next.next != null) {
        first = prev.next;
        second = first.next;
        // 交换节点
        prev.next = second;
        first.next = second.next;
        second.next = first;
        // 更新前指针
        prev = first;
    }
    return dummy.next;
}

思路简要说明

1. 哑节点解决头节点变化：交换第一对节点后，新的头节点会变成原来的第二个节点，所以用 dummy 指向原头节点，最后返回 dummy.next

2. 三个指针完成交换：prev 指向当前要交换的一对节点的前一个节点，first 和 second 分别指向要交换的两个节点

3. 判断是否还能交换：只有 prev.next 和 prev.next.next 都不为空时，后面才至少有两个节点，才能继续交换

三、思路详解

问题一：怎么返回新的头节点？

两两交换后，链表的头节点可能会改变

比如：

原链表：1 → 2 → 3 → 4
交换后：2 → 1 → 4 → 3

原来的头节点是 1，交换之后新的头节点变成了 2。如果直接拿原来的 head 返回，就会返回错误

最简单的解决办法是创建一个哑节点：

ListNode dummy = new ListNode(0, head);

让 dummy.next 指向原来的头节点。这样无论头节点怎么变化，dummy 始终在链表最前面，最后返回 dummy.next 即可

dummy → 1 → 2 → 3 → 4
        ↑
       head

交换第一对后：

dummy → 2 → 1 → 3 → 4
        ↑
   dummy.next（新的头节点）
            ↑
           head（原来的头节点1已经不是头节点了）

返回 dummy.next，也就是 2

可以看到，如果仍然返回原来的 head，返回的是节点 1，会丢失前面的节点 2；而返回 dummy.next，就能拿到真正的新头节点

问题二：怎么判断是否还能继续交换？

两两交换的前提是：后面至少还有两个节点

对于奇数个节点的链表，最后一个节点无法交换：

1 → 2 → 3 → 4 → 5
交换后：2 → 1 → 4 → 3 → 5

最后的 5 没有配对节点，所以保持不变

在代码中，我们用 prev 指向当前要交换的一对节点的前一个节点。那么要判断后面是否还有两个节点，只需要看：

while (prev.next != null && prev.next.next != null)

• prev.next != null：说明后面至少还有第一个节点
• prev.next.next != null：说明后面至少还有第二个节点

只有两个条件都满足，才能进行交换。只要其中一个为 null，就说明剩下的节点构不成一对，循环结束

问题三：怎么交换两个相邻节点？

这是本题最关键、也最抽象的地方

假设当前链表片段如下：

prev → first → second → next

我们想把 first 和 second 交换，变成：

prev → second → first → next

其中：

first = prev.next;
second = first.next;

也就是说，first 和 second 这两个节点已经被变量记录下来了，所以交换过程中不用担心丢失它们。真正需要注意的是：交换后还要让后面的 next 链表保持不变

交换步骤

交换的三行代码是：

prev.next = second;
first.next = second.next;
second.next = first;

我们逐步看：

第一步：让 prev 指向 second

prev.next = second;

原来：prev → first → second → next
现在：prev → second → next
       first ────────↑（first暂时还指向second）

这一步的作用是让前半段链表接到交换后的第一个节点 second

第二步：让 first 指向 second 后面的节点

first.next = second.next;

prev → second → next
       first  → next

这一步很关键：它把 first 接到后面的链表上，保证后续链表不会丢失

第三步：让 second 指向 first

second.next = first;

prev → second → first → next

到这里，两个节点交换完成

为什么交换顺序不能乱？

交换时最怕的就是断链或者丢失后续链表

如果一上来就写：

second.next = first;

那么 second 原本指向的 next 就会丢失，后面的链表接不上了

所以正确顺序是：

1. prev.next = second：让前面接到 second
2. first.next = second.next：让 first 接到后面的 next
3. second.next = first：最后让 second 指向 first，完成交换

这个顺序的关键是：先处理后续链表的连接，再完成反向指向

交换完成后如何继续下一轮？

交换完成后：

prev → second → first → next

此时 first 已经变成这对节点交换后的最后一个节点。下一轮要交换的是 first 后面的两个节点，所以需要：

prev = first;

这样下一轮的结构又变成：

prev → first → second → next

只不过这里新的 prev 是上一轮交换后的 first

举例说明

以 1 → 2 → 3 → 4 为例

初始状态：

dummy → 1 → 2 → 3 → 4
  ↑
 prev

第一轮交换 1 和 2：

first = 1
second = 2

交换前：dummy → 1 → 2 → 3 → 4

执行三步：
1. prev.next = second   ：dummy → 2
2. first.next = second.next ：1 → 3
3. second.next = first  ：2 → 1

交换后：dummy → 2 → 1 → 3 → 4
                  ↑
                 prev更新到1

第二轮交换 3 和 4：

prev = 1
first = 3
second = 4

交换前：dummy → 2 → 1 → 3 → 4

交换后：dummy → 2 → 1 → 4 → 3

最终返回：

2 → 1 → 4 → 3

• 时间复杂度：O(n)，每个节点只处理一次
• 空间复杂度：O(1)，只使用几个指针变量