24 两两交换链表中的节点

一、题目

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

二、题解

方法一：迭代法

思路：链表 + 虚拟头节点 + 指针交换。

1. 核心思路

由于题目要求不能交换节点的值，只能交换节点本身，所以需要通过修改链表节点之间的 next 指针来完成交换。

每次处理相邻的两个节点。

假设当前链表局部结构为：

prev -> first -> second -> next

交换后应该变成：

prev -> second -> first -> next

核心思想是：

  • 使用虚拟头节点 dummy，方便处理头节点也需要交换的情况；
  • 每次找到当前要交换的两个节点 first 和 second；
  • 通过修改指针顺序完成两个节点的交换。

2. 具体步骤

  1. 创建虚拟头节点 dummy，让 dummy.next = head。
  2. 定义指针 prev，表示当前要交换的两个节点的前一个节点。
  3. 当 prev.next 和 prev.next.next 都不为空时，说明后面至少还有两个节点，可以交换。
  4. 定义：
    • first = prev.next
    • second = prev.next.next
  5. 修改三个指针，完成交换。
  6. 将 prev 移动到下一组节点的前一个位置。
  7. 最后返回 dummy.next。

3. 关键逻辑

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

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

prev = first;

解释：

  • first 是当前这一组的第一个节点；
  • second 是当前这一组的第二个节点；
  • first.next = second.next，让第一个节点指向下一组的开头；
  • second.next = first，让第二个节点指向第一个节点；
  • prev.next = second，让前一个节点指向交换后的头节点；
  • 最后 prev = first，移动到下一组节点的前一个位置。

4. 代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 1. 创建虚拟头节点，方便处理头节点交换的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 2. prev 表示当前要交换的两个节点的前一个节点
        ListNode prev = dummy;

        // 3. 至少还剩两个节点时，才需要交换
        while (prev.next != null && prev.next.next != null) {
            // 当前这一组的第一个节点
            ListNode first = prev.next;

            // 当前这一组的第二个节点
            ListNode second = prev.next.next;

            // 交换两个节点
            first.next = second.next;
            second.next = first;
            prev.next = second;

            // prev 移动到下一组两个节点的前一个位置
            prev = first;
        }

        // 4. 返回新的头节点
        return dummy.next;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被访问一次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了几个指针变量，没有使用额外的数据结构，所以空间复杂度是 O(1)O(1)。

方法二：递归法

思路：递归 + 链表指针交换。

1. 核心思路

方法一使用迭代的方式从前往后交换节点，而方法二使用递归的方式处理链表。

递归的核心思想是：

  • 先交换当前链表的前两个节点；
  • 然后让后面的链表继续两两交换；
  • 最后把当前交换好的两个节点和后面交换好的链表连接起来。

假设当前链表为：

head -> second -> 后续链表

交换后应该变成：

second -> head -> 后续交换后的链表

2. 具体步骤

  1. 如果 head == null，说明链表为空，直接返回 head。
  2. 如果 head.next == null，说明只剩一个节点，不需要交换，直接返回 head。
  3. 定义 second = head.next，表示当前要交换的第二个节点。
  4. 递归处理 second.next 后面的链表。
  5. 让 head.next 指向后面已经交换好的链表。
  6. 让 second.next = head，完成当前两个节点的交换。
  7. 返回 second，因为交换后 second 是新的头节点。

3. 关键逻辑

ListNode second = head.next;

head.next = swapPairs(second.next);
second.next = head;

return second;

解释：

  • second 是当前这一组的第二个节点；
  • head.next = swapPairs(second.next)，表示当前第一个节点连接到后面已经交换好的链表；
  • second.next = head，表示第二个节点指向第一个节点，完成当前两个节点交换；
  • 返回 second，因为交换后 second 是当前链表的新头节点。

4. 代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 1. 如果链表为空，或者只剩一个节点，不需要交换
        if (head == null || head.next == null) {
            return head;
        }

        // 2. second 是当前要交换的第二个节点
        ListNode second = head.next;

        // 3. head 连接后面已经交换好的链表
        head.next = swapPairs(second.next);

        // 4. second 指向 head，完成当前两个节点的交换
        second.next = head;

        // 5. second 成为交换后的头节点
        return second;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被处理一次，所以时间复杂度是 O(n)O(n)。

空间复杂度：O(n)O(n)

说明：递归调用会占用系统栈空间，最多递归 n/2n / 2 层，所以空间复杂度是 O(n)O(n)。

评论