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

两两交换链表中的节点

题目
- 题目描述
- 示例 1：
- 示例 2：
- 示例 3：
- 提示：
- 题目链接
题解
- 解题思路
- python实现
- 代码解读
- 提交结果

题目

题目描述

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

示例 1：

在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

题目链接

两两交换链表中的节点

题解

解题思路

要解决这个问题，我们需要编写一个函数来交换链表中每两个相邻的节点。我们可以使用迭代或递归的方法来实现这一点。下面是用Python编写的迭代方法：

python实现

def swapPairs(head: ListNode) -> ListNode:# 创建一个哨兵节点（哑节点），它的next指针指向head。这有助于处理边界情况。dummy = ListNode(0)dummy.next = headprev_node = dummywhile head and head.next:# 初始化要交换的第一和第二个节点first_node = headsecond_node = head.next# 交换节点prev_node.next = second_nodefirst_node.next = second_node.nextsecond_node.next = first_node# 更新prev_node和head，为下一轮迭代做准备prev_node = first_nodehead = first_node.next# 返回新的头节点return dummy.next

代码解读

这段代码的工作原理如下：

我们首先创建了一个哨兵节点（也称为哑节点或伪头节点），它位于实际链表之前，并且其next属性指向链表的头节点。这个哨兵节点可以帮助我们更方便地处理链表头部的交换操作，因为它可以作为不变的起点。
接下来，我们进入一个循环，在这个循环中，只要当前节点(head)及其下一个节点都存在，我们就会进行交换。
在每次迭代中，我们将当前节点设置为first_node，将下一个节点设置为second_node。然后我们修改这些节点之间的链接以完成交换：前一个节点（prev_node）的next指针应该指向second_node，first_node的next指针应该指向second_node之后的节点，而second_node的next指针应该指向first_node。
完成交换后，我们更新prev_node为first_node，并且将head更新为first_node.next，即原来second_node的下一个节点，这样我们就准备好对链表中的下一对节点进行处理了。
当循环结束时，所有的节点已经被正确地两两交换了。我们返回哨兵节点的next，也就是新链表的头节点。