【LeetCode刷题日记：24】两两交换链表

前言：今天继续学习链表的相关题目，主要还是考察链表的基本操作，是面试的基础题常考，需要掌握。

题目背景：LeetCode24

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

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

题目答案：

第一种解法：

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;  
    }
}

题目解析：

我们这里仍旧使用虚拟头节点的方式，在做这种题目的时候，我们最好要把流程图画出来，不然容易搞混。

如图所示：我们把虚拟头节点设为cur，然后分别用临时节点保存需要移动的节点，我们这里保存的是第一个和第二个节点，关于temp记录的cur.next.next.next，实际上是为了步骤三交换位置。记录完之后，我们就可以开始交换了

首先cur.next=secondnode,secondnode.next=firstnode;

之后，交换后的firstnode节点的next，实际上就是我们下次开始执行交换的节点的下个节点，也就是我们保存的临时节点temp。

因为是两两交换，自然就是虚拟头节点的next.next.next,这里没什么深究的，而此时的firstnode也就相当于一开始虚拟头节点的作用，用于联系交换后面两个节点。

然后就是关于循环条件

如果链表有偶数个，那么循环的终止条件就是cur.next==null的时候，如图所示，执行完两次交换之后，此时的cur等于被交换之后val==3的那个位置

如图，因为是偶数节点，那么他后面的节点自然就是null

如果是奇数节点，我们画个图理解一下，那么也就是cur节点的next.next节点为null，因为cur.next的节点没有节点与之交换。

注意：这两个条件的位置一定不能交换，否则会报空指针异常

cur.next.next != null  // 先执行这个！
// cur.next = 节点1
// cur.next.next = 节点1.next = null
// 访问 null.next  → 💥 空指针异常！

注意： 其实我们在设置临时节点的时候，只需要保存cur.next和cur.next.next.next,的值，一般不需要设置第二个节点的临时节点去保存值，因为我们拿虚拟节点交换的时候 步骤一：cur.next=cur.next.next（也就是第二个节点变成了第一个节点，交换了位置） 步骤二：firstnode=cur.next.next;（这里如果不用firstnode去记录第一个节点，那么它的值已经在步骤一的时候就被覆盖了） 步骤三：照常

第二种解法：

// 递归版本
class Solution {
    public ListNode swapPairs(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }
} 

题目解析：

其实递归的本质就是代替循环的操作

链表初始状态： 1 → 2 → 3 → 4 → null

第一层调用 swapPairs(1)

• head = 1，head.next = 2，不为 null，不满足 base case
• next = head.next = 2
• 进入递归 newNode = swapPairs(3) （因为 next.next = 3）

第二层调用 swapPairs(3)

• head = 3，head.next = 4，不为 null
• next = head.next = 4
• 进入递归 newNode = swapPairs(5) （因为 next.next = null）

第三层调用 swapPairs(5)

• head = null → 满足 base case，返回 null
• 返回到第二层：newNode = null

回到第二层 swapPairs(3)

• next = 4，newNode = null
• 交换操作：
  1. next.next = head → 4.next = 3
  2. head.next = newNode → 3.next = null
• 此时链表局部：4 → 3 → null
• 返回 next → 返回节点 4

状态： 第二层返回到第一层的 newNode 是节点 4，且它带着 4 → 3 → null 这一段。

回到第一层 swapPairs(1)

• next = 2，newNode = 4 → 3 → null
• 交换操作：
  1. next.next = head → 2.next = 1
  2. head.next = newNode → 1.next = 4

注意此时 1.next = 4，所以链表变成： 2 → 1 → 4 → 3 → null

最终返回 next = 2，作为新的头节点返回。 完整结果：2 → 1 → 4 → 3 → null ✅

关键点总结：

• 递归从链表尾部向前建立两两交换后的链表
• 每次递归返回的是交换完这一对后，这一段的头节点（即原 next 节点）
• newNode 接收的是已经交换好的后续部分，然后挂在 head.next 上

补充：

为什么用 cur.next 而不是 dummyhead.next？

因为 cur 在移动，dummyhead 不动。当 cur 移动到后面时，cur.next 和 dummyhead.next 就完全不同了！

• cur.next：当前要交换的节点对的前一个节点
• dummyhead.next：整个链表的头节点（交换后会变化）

结语：

如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！