【算法分析与设计】两两交换链表中的节点

题目

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

示例

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

思想（虚拟头节点）

1. 简化边界情况： 虚拟头节点使得链表操作中的边界情况更容易处理。在没有虚拟头节点的情况下，你需要特殊处理头节点的交换，而使用虚拟头节点后，头节点就变得和其他节点一样，无需特殊处理。

2. 一致性： 使用虚拟头节点使得链表的头部始终存在，即使原始链表为空。这样，你可以始终将操作指向虚拟头节点，而无需检查链表是否为空。

3. 简化循环： 在循环中，虚拟头节点可以用作起始点，而不必关心当前节点是否为头节点。这样可以使循环体的逻辑更加简单。

4. 避免空指针异常： 在链表为空或只有一个节点时，如果没有虚拟头节点，可能会引发空指针异常。虚拟头节点确保链表始终有一个节点，从而避免了这种异常。

算法分析与设计

使用虚拟头节点：?创建一个虚拟头节点 dummy，并将其指向原始链表的头部。

ListNode dummy = new ListNode(0);

dummy.next = head;

ListNode prev = dummy;

循环遍历： 使用 while 循环遍历链表，确保至少有两个节点需要交换。循环条件为 head != null && head.next != null。

定义指针： 在循环内，定义两个指针 p 和 q 分别指向当前要交换的两个节点。

ListNode p = head; 
ListNode q = head.next;

交换节点： 交换 p 和 q 节点，同时更新相关的 next 指针。

p.next = q.next; 
q.next = p; 
prev.next = q;

更新指针： 更新 prev 和 head 指针，准备进行下一次交换。

prev = p; 
head = p.next;

循环结束： 循环结束后，返回虚拟头节点的 next，即交换后的链表头。

总体思路： 通过不断地交换相邻的两个节点，每次更新指针来保持链表的正确连接关系。在循环中，每次交换两个节点后，更新 prev、head 指针，确保下一次循环能够正确处理相邻的节点。循环结束后，返回虚拟头节点的 next，即交换后的链表头。

代码实现

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

        ListNode dummy = new ListNode(0); // 创建一个虚拟头节点
        dummy.next = head;
        ListNode prev = dummy;

        while (head != null && head.next != null) {
            ListNode p = head;
            ListNode q = head.next;

            // 交换节点
            p.next = q.next;
            q.next = p;
            prev.next = q;

            // 更新prev和head
            prev = p;
            head = p.next;
        }

        return dummy.next;
    }
}

运行结果

时间复杂度O(n)

空间复杂度O(1)