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

链表两两交换：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) {
             head;
        }
           head.next;
        head.next = swapPairsRecursive(nextNode.next);
        nextNode.next = head;
         nextNode;
    }

    
     ListNode  {
         (head ==  || head.next == ) {
             head;
        }
            ();
        dummy.next = head;
           dummy;

         (prev.next !=  && prev.next.next != ) {
               prev.next;
               prev.next.next;

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

            
            prev = first;
        }
         dummy.next;
    }

    
     ListNode  {
         (head ==  || head.next == ) {
             head;
        }
        
           head.next;
        head.next = newHead.next;
        newHead.next = head;
           head;

         (prev.next !=  && prev.next.next != ) {
               prev.next;
               prev.next.next;

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

            prev = first;
        }
         newHead;
    }
}