难度: Medium
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2：
输入：head = [] 输出：[]
示例 3：
输入：head = [1] 输出：[1]
提示：
- 链表中节点的数目在范围
[0, 100]内 0 <= Node.val <= 100
Submission
运行时间: 36 ms
内存: 16.9 MB
# 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]:
if head is None:
return
a = b = head
for i in range(2):
if b is None:
return head # last single node
b = b.next
def reverse_pair(head):
new_head = head.next
new_head.next = head
return new_head
new_head = reverse_pair(a)
a.next = self.swapPairs(b)
return new_head
Explain
该题解采用递归的方式来交换相邻的节点对。首先判断链表是否为空，如果为空则直接返回。然后定义两个指针a和b，初始时都指向头节点head。通过循环将b移动到第二个节点的位置，如果b为空则说明链表节点数为奇数，直接返回头节点。接着定义一个reverse_pair函数，用于交换一对相邻节点，并返回交换后的新头节点。然后递归调用swapPairs函数处理剩余的节点对，并将结果赋给a.next。最后返回新的头节点new_head。
时间复杂度: O(n)
空间复杂度: O(n)
# 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]:
# 如果链表为空，直接返回
if head is None:
return
# 定义两个指针a和b，初始都指向头节点
a = b = head
# 将指针b移动到第二个节点的位置
for i in range(2):
if b is None:
return head # 如果b为空，说明链表节点数为奇数，直接返回头节点
b = b.next
# 定义一个函数用于交换一对相邻节点
def reverse_pair(head):
new_head = head.next
new_head.next = head
return new_head
# 交换前两个节点，得到新的头节点
new_head = reverse_pair(a)
# 递归处理剩余的节点对
a.next = self.swapPairs(b)
# 返回新的头节点
return new_head
Explore
递归是处理链表问题的自然方法之一，因为它可以利用函数调用栈来反向追踪节点，而无需额外的数据结构。对于两两交换链表节点的问题，递归方法可以简洁地通过修改节点间的连接而非节点值来实现交换，尤其适用于无需访问链表以外的额外信息时。此外，递归允许将问题分解为可管理的小问题（如交换一对节点），这有助于简化逻辑和实现。
`reverse_pair`函数工作原理是调整节点间的链接，而不是更改节点的值。它接收一对节点作为输入，然后使第二个节点指向第一个节点，通过这种方式改变了节点间的指针而不触碰节点内的数据。这完全符合题目要求，即在交换节点时不改变节点内部的值。
在递归函数中，一旦交换了一对节点，函数会递归调用`swapPairs`处理当前对的下一对节点。这个调用的返回值将链接到已交换对的后一个节点上。这样，每对交换后的节点通过递归调用的返回值被正确地链接到剩余部分的链表上，从而保持了整个链表的连贯性和完整性。
如果节点总数为奇数，那么在移动指针`b`到第二个节点的过程中会发现`b`变为`None`（指向链表末尾之外）。这种情况下，说明没有足够的节点来形成一对，递归函数会直接返回当前的头节点`head`。这保证了单个未配对的节点保持在其原始位置，从而处理了奇数节点的边界条件。
递归方法的空间复杂度主要来自于递归调用栈。每进行一次递归调用，就会使用一定的栈空间，而总递归深度与链表长度n直接相关，大约为n/2，因此空间复杂度为O(n)。通过迭代方法，可以使用几个额外的指针变量来替代递归的栈空间，将空间复杂度降低到O(1)，这是因为迭代不依赖于调用栈。
在移动指针`b`时使用for循环是为了增加代码的健壮性和可读性。直接使用`head.next.next`假设链表至少有两个节点，这可能不总是情况。使用循环可以在每一步检查`b`是否为`None`，这样可以更安全地处理链表长度小于两个节点的情况，例如空链表或只有一个节点的链表。