24. 两两交换链表中的节点#

生活中的配对交换#

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

问题描述#

题目目标#

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

示例 1#

输入： 1 → 2 → 3 → 4 输出： 2 → 1 → 4 → 3 链表示意：

输入:  1 -> 2 -> 3 -> 4 -> null
输出:  2 -> 1 -> 4 -> 3 -> null

text

说明： 每两个相邻节点交换一次位置，所以结果变成了 2 -> 1 -> 4 -> 3。

示例 2#

输入： 1 → 2 → 3 输出： 2 → 1 → 3 链表示意：

输入:  1 -> 2 -> 3 -> null
输出:  2 -> 1 -> 3 -> null

text

说明： 每两个相邻节点交换一次位置，所以结果变成了 2 -> 1 -> 4 -> 3。

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

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

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

递归原理解析#

递归的精髓在于：

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

递归实现#

public ListNode swapPairs(ListNode head) {
    // 递归边界：空链表或只剩一个节点时，无需交换
    if (head == null || head.next == null) {
        return head;
    }

    // firstNode：当前这对节点中的第1个
    ListNode firstNode = head;
    // secondNode：当前这对节点中的第2个
    ListNode secondNode = head.next;

    // 递归处理剩余链表（从 third 节点开始），返回“后半部分交换后的头”
    ListNode remainingNodes = swapPairs(secondNode.next);

    // 先让 second 指向 first，完成当前对交换
    secondNode.next = firstNode;
    // 再让 first 接上后续已交换好的链表
    firstNode.next = remainingNodes;

    // 当前子问题的新头是 secondNode
    return secondNode;
}

java

复杂度分析#

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

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

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

迭代实现#

public ListNode swapPairs(ListNode head) {
    // dummy：虚拟头节点，便于统一处理头节点参与交换的情况
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    // prev：始终指向“当前待交换这一对节点”的前一个节点
    ListNode prev = dummy;

    // 条件：至少还剩两个节点可交换
    while (prev.next != null && prev.next.next != null) {
        // first/second：当前要交换的一对节点
        ListNode first = prev.next;
        ListNode second = prev.next.next;

        // 交换三步（顺序很关键）：
        // 1) 前驱接到 second
        prev.next = second;
        // 2) first 接到 second 的后继
        first.next = second.next;
        // 3) second 接到 first，完成局部翻转
        second.next = first;

        // prev 前移到交换后的尾节点 first，准备处理下一对
        prev = first;
    }

    // 返回交换后链表头（跳过 dummy）
    return dummy.next;
}

java

图解过程#

以链表 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

plaintext

两种解法的比较#

递归解法：

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

迭代解法：

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

编程技巧总结#

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

实际应用思考#

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

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

小结#

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

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

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

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

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