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）