两两交换链表中的节点

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

不能修改节点内部的值（即只能实际交换节点）。

解题思路

• 使用哑节点 dummy 简化头结点被交换的处理。
• 维护四个指针：
  • node0：当前待交换对的前驱节点（初始为 dummy）
  • node1：当前对的第一个节点
  • node2：当前对的第二个节点
  • node3：下一对的起始节点（node2 的后继）
• 交换步骤（重连指针）：
  • node0.next = node2
  • node2.next = node1
  • node1.next = 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)，只使用常数个指针。