两两交换链表中的节点：思路解析与代码实现

问题背景

给定一个单链表，要求将其中相邻的两个节点进行交换，并返回交换后的新头结点。需要注意的是，题目限制不能修改节点内部的值，只能实际交换节点本身。这是一个考察链表指针操作和边界处理的经典面试题。

核心思路

处理链表交换问题时，最头疼的往往是头结点被交换的情况。如果直接操作 head，需要单独判断；引入哑节点（dummy node）则能统一逻辑，让头结点的处理变得和普通节点一样。

我们需要维护四个指针来辅助重连：

• prev：当前待交换对的前驱节点，初始指向哑节点。
• first：当前对的第一个节点。
• second：当前对的第二个节点。
• next：下一对的起始节点（即 second 的后继）。

交换的核心在于调整 next 指向：

1. prev.next 指向 second，完成前驱到第二节点的连接。
2. second.next 指向 first，完成第二节点到第一节点的连接。
3. first.next 指向 next，完成第一节点到下一对的连接。

完成一次交换后，将 prev 移动到 first，first 移动到 next，继续循环。循环终止条件是 first 或 first.next 为空，确保每次都能成对处理。

代码实现

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 创建哑节点，简化头结点交换的处理
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode first = head;

        while (first != null && first.next != null) {
            ListNode second = first.next;
            ListNode next = second.next;

            // 断开并重连，完成一对交换
            prev.next = second;
            second.next = first;
            first.next = next;

            // 移动到下一对
            prev = first;
            first = next;
        }

        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n)。每个节点最多被访问一次，指针重连操作也是常数级。
• 空间复杂度：O(1)。只使用了固定数量的指针变量，没有额外分配内存。

这个解法在保持代码简洁的同时，能够高效地处理任意长度的链表，包括奇数长度时最后一个节点无需交换的情况。