【忍者算法】从手牵手到两两交换：探索链表节点的配对之舞｜LeetCode 24 两两交换链表中的节点

生活中的配对交换

想象一下排队买奶茶的场景：情侣们总喜欢两个人站在一起。如果队伍里的人想要实现"情侣相邻"，最简单的方法就是相邻两个人互换位置，直到所有人都找到适合的搭档。这就是我们今天要讨论的链表节点两两交换问题的现实映射。

问题描述

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

例如：

输入：1 → 2 → 3 → 4
输出：2 → 1 → 4 → 3

输入：1 → 2 → 3
输出：2 → 1 → 3

输入：1
输出：1

递归解法：优雅的节点交换

就像跳华尔兹舞时，每对舞伴都遵循同样的舞步，我们可以用递归的方式让每一对节点完成交换的舞蹈。

递归原理解析

递归的精髓在于：

1. 确定基本情况：当没有节点或只有一个节点时，无需交换
2. 找到重复模式：每次处理两个节点的交换
3. 链接新的关系：将交换后的部分与后续交换好的部分相连

递归实现

public ListNode swapPairs(ListNode head) {
    // 基本情况：空链表或只有一个节点
    if (head == null || head.next == null) {
        return head;
    }
    
    // 获取需要交换的两个节点
    ListNode firstNode = head;
    ListNode secondNode = head.next;
    
    // 递归处理后续节点
    ListNode remainingNodes = swapPairs(secondNode.next);
    
    // 执行交换
    secondNode.next = firstNode;
    firstNode.next = remainingNodes;
    
    return secondNode;
}

复杂度分析

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

迭代解法：舞伴交换的流水线

想象一个舞蹈教室，教练在指导多对舞伴依次交换位置。迭代解法就像是这个教练，一步步指导相邻节点完成交换。

迭代实现

public ListNode swapPairs(ListNode 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;
}

图解过程

以链表 1→2→3→4 为例：

1) 初始状态：
dummy → 1 → 2 → 3 → 4
  ↑
prev

2) 第一次交换后：
dummy → 2 → 1 → 3 → 4
          ↑
         prev

3) 第二次交换后：
dummy → 2 → 1 → 4 → 3
                ↑
               prev

两种解法的比较

递归解法：

• 优点：代码简洁优雅，思路清晰
• 缺点：需要额外的栈空间，对于长链表可能导致栈溢出
• 适用场景：链表较短，代码可读性要求高

迭代解法：

• 优点：空间效率高，适用于长链表
• 缺点：代码稍显复杂，需要维护多个指针
• 适用场景：对空间效率有要求，链表较长

编程技巧总结

1. 使用虚拟头节点简化边界处理
2. 画图理清指针变化顺序
3. 先确保局部交换正确，再考虑整体链接
4. 细心处理空指针情况

实际应用思考

这种两两交换的思想在实际编程中很有用：

• 数据压缩时的字节配对
• 网络通信中的数据包配对处理
• 并行计算中的任务配对

小结

两两交换链表节点的问题教会我们：

1. 如何优雅地处理链表节点的指针操作
2. 递归和迭代两种思维方式的应用场景
3. 在复杂操作中保持代码的清晰和健壮
4. 如何通过生活场景理解抽象的算法问题

建议：多思考类似的节点操作问题，它们都可以通过类似的思维方式解决：

• 链表反转
• K个一组反转链表
• 合并有序链表

记住：写代码如跳舞，优雅的节奏往往能带来最好的解决方案！

---

作者：忍者算法 公众号：忍者算法

我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～