两两交换链表中的节点：思路与实现

两两交换链表中的节点：思路与实现

问题背景

给定一个链表，要求两两交换其中相邻的节点，并返回交换后的链表。注意，不能修改节点内部的值，只能实际交换节点。

核心思路

处理链表头节点变化是个麻烦事，引入一个哑节点（dummy）能省去很多边界判断。我们需要四根'手指'来定位当前节点和下一组节点的关系：

• node0：当前待交换对的前驱节点，初始指向 dummy。
• node1：当前对的第一个节点。
• node2：当前对的第二个节点。
• node3：下一对的起始节点（即 node2 的后继）。

交换的核心在于指针的重连。只要确保 node0 指向 node2，node2 指向 node1，而 node1 指向 node3，这一对就交换成功了。之后将 node0 移到 node1 的位置，node1 移到 node3 的位置，继续处理下一对。循环条件设为 node1 与 node1.next 都非空，保证成对交换。

代码实现

下面是具体的实现逻辑，重点看指针重连的部分。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode node0 = dummy;
        ListNode node1 = head;
        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next;
            ListNode node3 = node2.next;
            
            // 断开并重连，完成一对交换
            node0.next = node2;
            node2.next = node1;
            node1.next = node3;
            
            // 移动到下一对
            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }
}

复杂度分析

时间上，每个节点至多被访问和指针重连一次，所以是 O(n)。空间上，只使用了常数个指针，不需要额外分配内存，空间复杂度为 O(1)。