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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

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

思路一（迭代法 / 虚拟头节点法）

两两交换相邻节点，本质上是按"两个一组"对链表进行局部反转。使用虚拟头节点（dummy head）可以统一处理头节点的交换操作，避免对头节点做特殊判断：

创建虚拟头节点 dummy_head，并将其 next 指向原链表头 head；
初始化 cur 指针指向虚拟头节点；
当 cur.next 和 cur.next.next 都存在时（即当前组至少有两个节点），进行交换：
- 记 first = cur.next、second = cur.next.next；
- 将 first.next 指向 second.next（保存后续节点）；
- 将 second.next 指向 first（反转当前组）；
- 将 cur.next 指向 second（接入已交换的组）；
- 将 cur 移动到 first（即下一组的前一个节点）；
循环结束后，返回 dummy_head.next。

该思路时间复杂度为 O(n)，空间复杂度为 O(1)。

解法一（迭代法）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy_head = ListNode(0)
        dummy_head.next = head
        cur = dummy_head

        # 必须保证当前组有两个节点
        while cur.next and cur.next.next:
            first = cur.next
            second = cur.next.next

            # 三步反转：first.next 暂存后续；second.next 指向 first；cur.next 指向 second
            first.next = second.next
            second.next = first
            cur.next = second

            # cur 移动到当前组的后一个节点（即 first），作为下一组的前驱
            cur = first

        return dummy_head.next

解释一（迭代法代码解释）

代码片段	作用与原因
`dummy_head = ListNode(0); dummy_head.next = head`	创建虚拟头节点，统一处理头节点的交换逻辑，避免对头节点做特殊判断
`cur = dummy_head`	cur 永远指向当前要交换的"两个节点"的前一个节点
`while cur.next and cur.next.next:`	循环条件：保证当前组至少有两个节点可交换
`first = cur.next; second = cur.next.next`	暂存当前要交换的两个节点，便于后续操作
`first.next = second.next`	关键步骤 1：先把 first 与后续节点断开，把 first 指向 second 的下一个节点（即下一组的起点）
`second.next = first`	关键步骤 2：反转当前组，second 指向 first
`cur.next = second`	关键步骤 3：把当前组重新接到链表上，cur.next 指向已交换后的新头 second
`cur = first`	cur 后移两步（first 已经被交换到 second 后面），准备处理下一组
`return dummy_head.next`	返回虚拟头节点的下一个节点，即交换后链表的新头节点

思路二（递归法）

利用递归"自顶向下"的思想，从链表头部开始两两交换：

递归终止条件：链表为空或只有一个节点时，无需交换，直接返回 head；
递归处理：先保存 new_head = head.next（即交换后的新头节点）；
将 head.next 指向"剩余子链表两两交换后的结果"，即 head.next = self.swapPairs(head.next.next)；
将 new_head.next 指向 head，完成当前组的反转；
返回 new_head 作为本层递归的结果。

该思路时间复杂度为 O(n)，空间复杂度为 O(n)（递归调用栈）。

解法二（递归法）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # 递归终止：空链表或单节点
        if not head or not head.next:
            return head

        # new_head 是本组交换后的新头节点
        new_head = head.next
        # head.next 指向"剩余子链表"两两交换后的结果
        head.next = self.swapPairs(head.next.next)
        # new_head.next 指向 head，完成当前组的反转
        new_head.next = head

        return new_head

解释二（递归法代码解释）

代码片段	作用与原因
`if not head or not head.next: return head`	递归终止条件：空链表或只有一个节点时无需交换，直接返回
`new_head = head.next`	保存本组交换后的新头节点（即原 head 的下一个节点）
`head.next = self.swapPairs(head.next.next)`	核心：递归处理从 `head.next.next` 开始的子链表，递归结果接到 head 之后
`new_head.next = head`	完成当前两节点的反转：new_head 指向 head
`return new_head`	将本组交换后的新头节点 new_head 一路向上回传

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