链表两两交换：Java 递归与迭代三种实现方案

链表操作是面试中的高频考点，尤其是涉及指针重连的场景。掌握'两两交换'这类问题，能帮你深入理解链表的指针操作和递归思维。与其死记硬背，不如跟着思路走一遍，自己动手写写代码，很快就能独立解决这类变体。

为什么需要交换？

生活中很多场景都涉及'顺序调整'。比如排队买东西，队伍里的人两两交换位置；或者整理书架，把相邻的两本书互换。在算法中，这对应着链表节点指针的重新指向。

实际业务中也有类似需求：

数据排序：用户列表局部重排，用于 A/B 测试。
任务调度：队列中优先级相邻任务交换，提升效率。
游戏设计：排行榜动态调整玩家位置。

三种解法深度解析

1. 递归法：直观但消耗栈空间

递归的核心思想很简单：处理当前一对节点，然后递归处理剩余部分。

思路：

终止条件：当前节点为空或下一个节点为空。
交换当前两个节点，将第一个节点的 next 指向递归结果。
返回新的头节点（即原来的第二个节点）。

这种方式代码最简洁，但要注意递归深度。如果链表很长，可能会导致栈溢出。

时间复杂度：O(n)，每个节点访问一次。 空间复杂度：O(n)，递归调用栈。

2. 迭代法（带哑节点）：工程实践首选

这是最推荐的写法。引入一个哑节点（dummy node）作为虚拟头，可以统一处理头节点变化的情况，避免特殊判断。

关键点：

使用 prev 指针记录前一对节点的后继。
每次循环处理 first 和 second 两个节点。
更新指针后，移动 prev 到下一对之前。

时间复杂度：O(n)。 空间复杂度：O(1)。

3. 迭代法（无哑节点）：直接操作头节点

不引入辅助节点，直接修改头节点。逻辑稍繁琐，因为第一次交换可能改变头指针，后续则不需要。适合对内存极其敏感的场景，但维护成本略高。

代码实现

下面是完整的 Java 实现，包含三种方法。你可以直接复制运行验证。

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    // 解法 1：递归
    public ListNode swapPairsRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode nextNode = head.next;
        head.next = swapPairsRecursive(nextNode.next);
        nextNode.next = head;
        return nextNode;
    }

    // 解法 2：迭代（带哑节点）
    public ListNode swapPairsIterative(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;

            // 交换指针
            prev.next = second;
            first.next = second.next;
            second.next = first;

            // 移动到下一组
            prev = first;
        }
        return dummy.next;
    }

    // 解法 3：迭代（无哑节点）
    public ListNode swapPairsDirect(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 先处理头两个节点
        ListNode newHead = head.next;
        head.next = newHead.next;
        newHead.next = head;
        ListNode prev = head;

        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = prev.next.next;

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

            prev = first;
        }
        return newHead;
    }
}

总结与建议

在实际开发中，**迭代法（带哑节点）**通常是最佳选择。它避免了递归栈溢出的风险，且逻辑清晰，容易维护。如果是面试场景追求代码量最少，递归法也不错，但要准备好解释空间复杂度。

记住，链表操作的核心在于'画图'。在纸上画出指针变化，比盯着代码看更容易理解。多练习几遍，这种指针切换就会变成肌肉记忆。