当前位置：首页 > news >正文

链表题解——两两交换链表中的节点【LeetCode】

news 2025/7/1 9:37:05

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

一、算法逻辑（通顺讲解每一步的思路）

这段代码使用的是递归方式来解决链表中节点的两两交换问题。其整体处理过程如下：

1️⃣ 递归终止条件：处理边界情况

当链表为空或链表只剩下一个节点时，说明已经不足两个节点可以交换了。这时直接返回当前节点，递归结束。

2️⃣ 提取当前要交换的两个节点

在可以交换的前提下，取当前链表的前两个节点作为一对（设为 node1 和 node2）。它们将进行交换操作。

3️⃣ 递归处理后续链表

取出 node2 后的链表头节点（即 node3），然后对从 node3 开始的链表递归调用 swapPairs，此时链表被自然拆分为前后两部分：当前这对 + 后续部分。

4️⃣ 构建当前这一对的交换结构

将 node1 的 next 指针指向递归结果（即后续已完成交换的链表），再让 node2 的 next 指向 node1，完成当前两个节点的交换。

5️⃣ 返回新的子链表头节点

最终将 node2 作为这一对节点交换后的新头节点返回，作为上一层递归链接的入口。

二、核心点总结

该递归算法的核心在于以下三点：

将问题局部化：只处理当前两个节点，其余部分交给递归；
天然递归拼接结构：每一对交换完成后，通过递归返回值自然连接；
思路简洁清晰：每次递归都只处理“两两交换”这个最小问题单元。

所以整体的核心思路可以概括为一句话：

“局部交换 + 递归合并”。

# 递归版本class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:  # 递归边界return head  # 不足两个节点，无需交换node1 = headnode2 = head.nextnode3 = node2.nextnode1.next = self.swapPairs(node3)  # 1 指向递归返回的链表头node2.next = node1  # 2 指向 1return node2  # 返回交换后的链表头节点

代码执行示例

假设链表为：1 -> 2 -> 3 -> 4 -> None

执行过程：

第一次递归调用：
- pre = 1，cur = 2，next = 3
- 交换 pre 和 cur：2 -> 1
- 递归处理 next = 3，得到交换后的链表 4 -> 3
- 将 pre.next（即 1.next）指向 4 -> 3，最终链表为 2 -> 1 -> 4 -> 3 -> None
- 返回 cur = 2，即交换后的新链表头节点。