LeetCode 两两交换链表中的节点：Java 递归与迭代解法 | 极客日志

Javajava算法

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

LeetCode 第 24 题“两两交换链表中的节点”。要求在不修改节点值的情况下，通过调整指针成对交换相邻节点。文章提供了递归和迭代两种 Java 解法，重点分析了哑节点的使用及指针操作顺序。迭代法空间复杂度为 O(1)，推荐用于生产环境。内容涵盖复杂度分析、常见问题解答及实际应用场景，帮助读者掌握链表核心操作技巧。

疯疯癫癫发布于 2026/3/25更新于 2026/4/177 浏览

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

一、原题回顾

题目描述： 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

输入：head =  输出：

输入：head = [] 输出：[]

输入：head = [1] 输出：[1]

/**
 * 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;
    }
}

方法	时间复杂度	空间复杂度	是否修改节点值
递归	O(n)	O(n)	❌（仅改指针）
迭代	O(n)	O(1)	❌

// 示例：单元测试用例
@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]))));
}

维度	递归	迭代
代码简洁性	✅ 高	❌ 中
空间效率	❌ O(n)	✅ O(1)
可读性	✅ 直观	❌ 需理解指针
栈溢出风险	✅ 存在	❌ 无

题号	题目	关联点
206. 反转链表	链表基本操作	指针重定向
92. 反转链表 II	区间反转	哑节点 + 指针操作
25. K 个一组翻转链表	本题扩展	分组处理
143. 重排链表	找中点 + 反转 + 合并	综合应用
86. 分隔链表	哑节点	链表分隔
328. 奇偶链表	重排	指针分离

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

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

一、原题回顾

二、原题分析

核心难点：

关键观察：

三、答案构思

思路 1：递归（自顶向下）

思路 2：迭代（自底向上）

四、完整答案（Java 实现）

方法一：递归解法

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

五、代码分析

1. 递归解法详解

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

3. 哑节点的作用

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

七、常见问题解答（FAQ）

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

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

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

Q4：能否用栈实现？

八、优化思路

1. 提前退出优化

2. 减少临时变量

3. 工程化增强

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

1. 链表操作核心原则

2. 哑节点（Dummy Node）

3. 递归 vs 迭代

4. 指针操作黄金法则

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

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

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

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

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

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

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

2. 音频/视频帧处理

3. 任务调度队列

4. 链表操作的通用训练

十二、相关题目推荐

十三、总结与延伸

✅ 本题核心收获

🔮 延伸思考

🌟 最后建议

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

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

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