24.两两交换链表中的节点

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

解题思路

我的思路：

1. 设定虚拟头节点 dummy，方便处理边界情况
2. 设定指针 pre 指向当前处理对的前一个节点
3. 进入循环，pre.next != null && pre.next.next != null 确保至少有两个节点可以交换
   1. 设定指针 first 指向第一个需要交换的节点，second 指向第二个需要交换的节点
   2. first 节点的 next 指针原本指向 second 节点，现在令其指向 second 的下一个节点
   3. 令 second 节点的 next 指针指向 first 节点
   4. pre 节点的 next 指针原来指向 first 节点，现在令其指向 second 节点
   5. 移动 pre 指针到下一对需要交换的节点前，也就是指向 first 节点

我的代码

public ListNode swapPairs(ListNode head) {
    // 设置一个虚拟头结点，方便处理边界情况
    ListNode dummy = new ListNode(0, head);
    // pre 指向当前处理对的前一个节点
    ListNode pre = dummy;
    // 循环条件确保至少有两个节点可以交换
    while (pre.next != null && pre.next.next != null) {
        ListNode first = pre.next;    // 第一个需要交换的节点
        ListNode second = first.next; // 第二个需要交换的节点

        // 交换操作
        first.next = second.next;
        second.next = first;
        pre.next = second;
        
		// 移动 pre 到下一对需要交换的节点前
        pre = firstNode;
    }
    // 返回新链表的头节点
    return dummy.next;
}

时间复杂度：O(n)

空间复杂度：O(1)

总结

如果使用 C，C++ 编程语言的话，不要忘了还要从内存中删除这两个移除的节点。

当然如果使用 Java ，Python 的话就不用手动管理内存了。

注意虚拟头节点的引入，可以使代码逻辑更统一。