1 题目描述

24. 两两交换链表中的节点要求给定一个链表，要求两两交换其中相邻的节点，并返回交换后链表的头节点。需要注意的是，必须在不修改节点内部的值的情况下完成这个任务（即，只能进行节点交换）。

2 解题思路

为了实现两两交换，我们可以采用迭代的方法。首先定义一个哑节点（dummy node），它的 next 指向原链表的头节点 head。这样做的好处是可以简化边界情况的处理。接下来，每次迭代中，我们都会处理两个节点，并将它们交换位置。具体步骤如下：

1. 初始化三个指针：prev 指向前一个节点（初始为哑节点），curr 指向当前节点（初始为 head），next 指向下一个节点（初始为 curr.next）。
2. 在每一轮迭代中，先保存 curr.next，即 next；然后让 curr.next 指向 next.next，即下一个节点之后的节点。
3. 接着，调整 next 和 curr 的关系，使 next 指向 curr，而 curr 应该指向 next.next。
4. 最后，更新 prev.next 指向 next，完成这次交换。
5. 更新 prev 和 curr，继续下一轮迭代，直到 curr 为空或者 curr.next 为空。

3 Java 代码实现

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // 引入哑节点简化代码逻辑
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;
        
        while (curr.next != null && curr.next.next != null) {
            // 指向第一个节点
            ListNode first = curr.next;
            // 指向第二个节点
            ListNode second = curr.next.next;
            
            // 第一个节点指向下一对的第一个节点
            first.next = second.next;
            // 当前节点指向下一对的第二个节点
            curr.next = second;
            // 第二个节点指回第一个节点
            second.next = first;
            
            // 更新当前节点
            curr = first;
        }
        
        return dummy.next;
    }
}

• 时间复杂度: O(n)，其中 n 是链表中的节点数量。每个节点最多被处理两次。
• 空间复杂度: O(1)，除了几个指针变量外，没有使用额外的空间。

4 注意事项

• 哑节点：引入哑节点 dummy 以简化代码逻辑，避免处理头节点的特殊情况。
• 遍历链表：使用 curr 指针来遍历链表，处理每一对节点。
• 节点交换：每次将当前节点与其下一个节点交换位置，调整指针关系。
• 退出条件：当当前节点后面没有足够两个节点时，停止遍历。