LeetCode 两两交换链表中的节点：Java 递归与迭代解法

📌 共同技巧：引入'哑节点' 创建 dummyHead，其 next = head，确保无论是否交换头节点，都能通过 dummyHead.next 返回正确结果。

四、完整答案（Java 实现）

方法一：递归解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归终止条件：空链表或只剩一个节点
        if (head == null || head.next == null) {
            return head;
        }
        // 记录新的头节点（原第二个节点）
        ListNode newHead = head.next;
        // 递归处理后续节点，并将结果接在原 head 后面
        head.next = swapPairs(newHead.next);
        // 将 newHead 指向原 head，完成交换
        newHead.next = head;
        return newHead;
    }
}

方法二：迭代解法（推荐！）

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建哑节点，简化头节点处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        // temp 始终指向当前待交换对的前驱
        ListNode temp = dummyHead;
        // 只要后面还有至少两个节点，就继续交换
        while (temp.next != null && temp.next.next != null) {
            // 获取要交换的两个节点
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            // 执行交换操作（关键三步）
            temp.next = node2;          // 前驱指向 node2
            node1.next = node2.next;    // node1 指向 node2 的下一个
            node2.next = node1;         // node2 指向 node1
            // 移动 temp 到下一对的前驱（即当前对的尾节点）
            temp = node1;
        }
        return dummyHead.next;
    }
}

✅ 强烈推荐迭代解法：空间效率高，无递归开销，更适合生产环境。

五、代码分析

1. 递归解法详解

以 [1,2,3,4] 为例：

• 第一层：head=1, newHead=2 → 1.next = swapPairs(3)
• 第二层：head=3, newHead=4 → 3.next = swapPairs(null) = null
• 回溯：4.next = 3 → 返回 4
• 回溯：1.next = 4，2.next = 1 → 返回 2
• 最终：2 → 1 → 4 → 3

关键点：

• head.next = swapPairs(...)：将原第一个节点的 next 指向后续交换后的头节点；
• newHead.next = head：完成当前对的交换。

2. 迭代解法指针操作（重点！）

交换前：temp → node1 → node2 → nextGroup... 交换后：temp → node2 → node1 → nextGroup...

三步操作顺序至关重要：

1. temp.next = node2 → 先让前驱指向新头（否则会丢失 node2）
2. node1.next = node2.next → 让原第一个节点指向下一组（保存后续链表）
3. node2.next = node1 → 完成当前对的反转

⚠️ 错误顺序示例： 若先执行 node2.next = node1，则 node2.next 被覆盖，无法获取 nextGroup！

3. 哑节点的作用

• 原链表：1 → 2 → 3 → 4
• 加哑节点：dummy → 1 → 2 → 3 → 4
• 交换后：dummy → 2 → 1 → 4 → 3
• 返回 dummy.next 即 2，无需特殊判断头节点是否变化。

六、时间复杂度和空间复杂度分析

其中 n 为链表节点数。

• 时间：每个节点被访问一次，O(n)
• 空间：
  • 递归：调用栈深度 ≈ n/2 → O(n)
  • 迭代：仅用常数个指针 → O(1)

💡 工程建议：优先使用迭代，避免递归潜在风险（即使本题安全）。

七、常见问题解答（FAQ）

Q1：为什么不能直接交换 val？

答：题目明确要求'只能进行节点交换'。在真实系统中，节点可能包含大量数据（如用户对象），交换指针比复制数据高效得多。此外，某些场景下节点是不可变的（immutable），无法修改 val。

Q2：迭代中 temp = node1 是什么意思？

答：交换后，node1 成为当前对的尾节点，它自然就是下一对节点的前驱。例如：初始：dummy → 1 → 2 → 3 → 4 交换第一对后：dummy → 2 → 1 → 3 → 4 此时 temp 应指向 1，以便下一轮交换 3 和 4

Q3：如果链表长度为奇数怎么办？

答：最后一节点自动保留。例如 [1,2,3] → [2,1,3]。 因为循环条件是 temp.next != null && temp.next.next != null，当只剩一个节点时，循环终止。

Q4：能否用栈实现？

答：可以，但效率低。遍历链表入栈，然后每次弹出两个节点重新连接。但空间 O(n)，且需两次遍历，不推荐。

八、优化思路

1. 提前退出优化

在迭代开始前检查 head == null || head.next == null，直接返回。但收益微乎其微。

2. 减少临时变量

可合并部分操作，但会降低可读性，不建议。

3. 工程化增强

• 添加日志：记录交换过程
• 输入校验：虽然题目保证范围，但生产代码应防御性编程
• 单元测试：覆盖空、单节点、偶数、奇数长度

// 示例：单元测试用例
@Test
void testSwapPairs() {
    assertEquals(asList(2, 1, 4, 3), toList(swapPairs(toListNode([1, 2, 3, 4]))));
    assertEquals(Collections.emptyList(), toList(swapPairs(toListNode([]))));
    assertEquals(asList(1), toList(swapPairs(toListNode([1]))));
}

九、数据结构与算法基础知识点回顾

1. 链表操作核心原则

• 删除/插入：必须通过前驱节点操作
• 反转：调整 next 指针方向
• 交换：本质是指针重定向，非值交换

2. 哑节点（Dummy Node）

• 作用：消除头节点特殊处理
• 适用场景：任何可能改变头节点的链表操作（删除、反转、合并等）

3. 递归 vs 迭代

4. 指针操作黄金法则

• 先保存：在断开指针前，保存需要的引用
• 再连接：按依赖顺序更新指针
• 画图辅助：复杂操作务必画图验证

十、面试官提问环节（模拟）

❓ 问题 1：你的迭代解法中，为什么需要三个指针？

回答： 实际上我们用了四个引用：temp, node1, node2, 以及隐式的 node2.next。 原因是：要完成 A→B→C→D 到 A→C→B→D 的转换，必须同时知道：A（前驱，用于连接 C）B（原第一个，需指向 D）C（原第二个，需指向 B）D（后续链表头） 缺少任何一个，都会导致链表断裂。

❓ 问题 2：如果要求每 k 个节点一组反转，你会怎么做？

回答： 这是 LeetCode 第 25 题《K 个一组翻转链表》。 思路：先检查后续是否有 k 个节点；若有，反转这 k 个节点（可用迭代反转子链表）；递归或迭代处理下一组；连接各组。 本题是 k=2 的特例。

❓ 问题 3：你的解法能处理环形链表吗？

回答： 不能，且题目假设链表无环。 若存在环，递归会无限调用导致栈溢出；迭代会陷入死循环。 实际工程中，应先用快慢指针检测环（Floyd 算法），再处理。

❓ 问题 4：为什么不用 Collections.swap()？

回答： Collections.swap() 适用于 List 接口（如 ArrayList），但链表（LinkedList）虽实现 List，其 swap 本质仍是交换值，而非节点。 且本题输入是 ListNode 自定义结构，非 Java 集合。

十一、这道算法题在实际开发中的应用

虽然'两两交换'看似抽象，但其思想在实际系统中广泛应用：

1. 网络协议中的数据包重组

• 某些协议要求数据包成对处理（如 ACK 机制）
• 链表可表示数据包队列，交换操作模拟重排

2. 音频/视频帧处理

• 音频采样点或视频帧有时需成对交换以实现特效（如立体声左右声道互换）
• 若用链表存储帧，此操作可高效完成

3. 任务调度队列

• 某些调度策略要求交替执行两类任务（A-B-A-B → B-A-B-A）
• 通过交换队列中相邻任务实现策略切换

4. 链表操作的通用训练

• 本题是指针操作的经典练习
• 掌握后可轻松应对更复杂的链表变形（如反转、合并、分隔）

💡 核心价值：培养对内存布局和指针语义的直觉，这是系统编程的基础。

十二、相关题目推荐

掌握本题后，可挑战以下 LeetCode 题目：

建议按顺序练习，逐步提升链表操作能力。

十三、总结与延伸

✅ 本题核心收获

1. 链表交换的本质：通过指针重定向实现节点位置变更，而非值交换；
2. 哑节点的威力：统一处理头节点变更，避免大量 if-else；
3. 递归 vs 迭代：理解两种范式的适用场景，优先选择空间高效的迭代；
4. 指针操作顺序：必须'先保存，再连接'，画图是避免 bug 的最佳实践。

🔮 延伸思考

• 双向链表如何交换？ 需额外维护 prev 指针，操作更复杂，但逻辑类似。
• 能否原地交换而不使用哑节点？ 可以，但需单独处理头节点，代码冗余且易错。
• 函数式解法？ 在支持模式匹配的语言（如 Scala）中，可用递归 + 模式匹配优雅实现。

🌟 最后建议

• 手写代码：在白板上写出迭代解法，确保指针操作无误；
• 讲清思路：面试时先说'我打算用哑节点 + 迭代'，再解释三步交换；
• 主动测试：提出测试 [1,2,3]、[1,2]、[] 等 case，展现工程素养。

'链表题，指针是笔，内存是纸，画图是草稿。' 掌握本题，你就拥有了处理复杂链表变形的钥匙。