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

**两两交换链表中的节点**

###问题描述给定一个单链表的头指针 `head`，每个结点包含一个整数值。请将链表中所有结点按顺序进行两两交换。

### 示例输入：1 ->2 ->3 ->4输出：2 ->1 ->4 ->3### 解决方案#### 方法一：迭代法

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef swapPairs(head: ListNode) -> ListNode:
 # 如果链表为空或只有一个结点，则不需要交换 if not head or not head.next:
 return head # 将头结点和下一个结点进行两两交换 new_head = head.next head.next = swapPairs(new_head.next)
 new_head.next = head return new_head

#### 方法二：递归法

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef swapPairs(head: ListNode) -> ListNode:
 # 如果链表为空或只有一个结点，则不需要交换 if not head or not head.next:
 return head # 将头结点和下一个结点进行两两交换 new_head = head.next head.next = swapPairs(new_head.next)
 new_head.next = head return new_head# 测试用例def printList(head: ListNode) -> None:
 while head:
 print(head.val, end=" ")
 head = head.next print()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

print("原链表：")
printList(head)

new_head = swapPairs(head)

print("交换后链表：")
printList(new_head)

###代码注释* `swapPairs`函数用于将链表中所有结点进行两两交换。
* 如果链表为空或只有一个结点，则不需要交换，直接返回原链表的头指针。
* 将头结点和下一个结点进行两两交换，更新新链表的头指针和下一个结点。
* 递归函数 `swapPairs`用于交换链表中所有结点。

### 时间复杂度* 最坏情况下，链表中的结点数为 n，时间复杂度为 O(n)。
* 在最优情况下，链表中只有一个结点，时间复杂度为 O(1)。

### 空间复杂度* 使用递归函数 `swapPairs`时，空间复杂度为 O(h)，其中 h 为链表的高度（从头指针到尾指针）。
* 在最坏情况下，链表中的结点数为 n，空间复杂度为 O(n)。
* 在最优情况下，链表中只有一个结点，空间复杂度为 O(1)。

### 总结两两交换链表中的节点是一个经典的链表操作问题。使用迭代法或递归法都可以实现这个功能。时间复杂度和空间复杂度分别为 O(n) 和 O(h)，其中 h 为链表的高度。