【Leetcode】24. 两两交换链表中的节点

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

### 题目描述给定一个单链表的头节点 `head`，请将其转换为交替链表。交替链表是指每个节点的值都大于或等于上一个节点的值。

### 示例1:

输入:`1 ->2 ->3 ->4`

输出:`1 ->3 ->2 ->4`

### 示例2:

输入:`1 ->5 ->9`

输出:`1 ->9 ->5`

### 思路我们可以使用一个辅助链表来存储交替链表的节点。每次将两个相邻的原链表中的节点取出，并将它们插入到辅助链表中。

###代码实现

# Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
 self.val = x self.next = Noneclass Solution:
 def swapPairs(self, head: ListNode) -> ListNode:
 # 如果链表为空或只有一个节点，则不需要交换 if not head or not head.next:
 return head # 将头结点和下一个结点取出 first_node = head second_node = head.next # 将第二个结点的next指向第三个结点 first_node.next = self.swapPairs(second_node.next)
 # 将第一个结点的next指向第二个结点 second_node.next = first_node return second_node# 测试用例def printList(head):
 while head:
 print(head.val, end=" -> ")
 head = head.next print("None")

if __name__ == "__main__":
 # 创建链表1 ->2 ->3 ->4 head = ListNode(1)
 head.next = ListNode(2)
 head.next.next = ListNode(3)
 head.next.next.next = ListNode(4)

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

 solution = Solution()
 new_head = solution.swapPairs(head)

 print("交替链表:")
 printList(new_head)

###代码注释* `swapPairs`函数是解决这个问题的核心函数。它首先检查链表是否为空或只有一个节点。如果是，则直接返回原链表。
* 如果链表有两个或以上的节点，函数会取出头结点和下一个结点，将它们作为交替链表中的第一个和第二个结点。
* 然后，它将第二个结点的 `next`指向第三个结点（通过递归调用 `swapPairs`函数），并将第一个结点的 `next`指向第二个结点，完成交替链表的构建。
* 最后，函数返回新的头结点，即交替链表中的第一个结点。

### 测试用例在测试用例中，我们首先创建一个链表1 ->2 ->3 ->4，然后使用 `swapPairs`函数将其转换为交替链表。最后，我们打印出原链表和交替链表的值，以验证结果。

### 总结通过使用递归和辅助链表来存储交替链表中的节点，我们可以有效地解决这个问题。测试用例和代码注释都有助于理解解决方案的逻辑和实现细节。