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

题目链接：24. 两两交换链表中的节点

题目描述

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

核心思考：虚拟头节点与多指针穿针引线

涉及到修改链表头部的操作（比如这里的第一个和第二个节点交换后，头节点会立刻发生变化），最优实践总是引入一个虚拟头节点 (dummy node)，让这棵人造的虚拟头节点统一我们对所有真实节点的操作逻辑。

以 [1, 2, 3, 4] 为例，两两交换需要动用四个关键锚点才能确保牵线搭桥不出错：

1. node0（当前操作对的前驱，例如 dummy）
2. node1（当前需要被交换的第一个节点 1）
3. node2（当前需要被交换的第二个节点 2）
4. node3（操作对的后继，即节点 3）

交换四步曲：

• node0 接向 node2。
• node2 接回 node1。
• node1 抛向后方接上 node3。
• 完成这一组后，将双游标平移，预备下一组：node0 = node1 且 node1 = node3。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node0 = dummy = ListNode(next=head)
        node1 = head
        while node1 and node1.next:
            node2 = node1.next
            node0.next = node2
            node3 = node2.next
            node2.next = node1
            node1.next = node3

            node0 = node1
            node1 = node3
        return dummy.next

复杂度分析

• 时间复杂度：O(N)，其中 N 是链表中的节点总数量。我们依次步进遍历了所有的原始节点，每一个节点都被处理且只交换一次。
• 空间复杂度：O(1)，引入了虚拟头节点以及一组辅助的独立游标，所需的仅为常数级别的内存。