【力扣算法19】之 24. 两两交换链表中的节点 python

问题描述

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

示例1

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

示例2

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

示例3

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

提示

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

思路分析

这个问题要求我们对给定链表中的节点进行两两交换，并返回交换后的链表。我们需要在不修改节点的值的情况下完成交换，只能通过调整节点之间的连接关系来实现。

我们可以使用递归的方法解决这个问题。

1. 首先判断当前链表是否为空或者只有一个节点。如果是，则无需交换，直接返回原链表。
2. 如果链表中至少有两个节点，我们可以将第一个节点和第二个节点进行交换。交换后，第二个节点变为新的头节点，第一个节点变为新的第二个节点。
3. 我们将原链表的头节点指向第二个节点，即交换后的新头节点。然后，将原头节点的next指针指向递归调用swapPairs函数的返回结果，即第三个节点和后面节点交换后的链表。
4. 最后，返回交换后的新头节点。

递归函数的终止条件是当前链表为空或者只有一个节点。

这种递归的思路可以保证每次交换一对节点，并正确地连接它们与后面的节点。

例如，对于链表[1,2,3,4]，按照上述步骤进行交换：

• 首先交换1和2，得到新的头节点2，1成为新的第二个节点。
• 原头节点1的next指向递归调用swapPairs函数的结果，即4和后面节点交换后的链表。
• 递归调用处理4和后面节点交换的过程，得到新的头节点4。
• 最后将2的next指针指向4，完成整个链表的交换。

代码分析

首先， 检查当前链表是否为空或者只有一个节点。如果是，说明无需交换，直接返回原链表。 然后， 定义两个指针prev和cur，分别指向要交换的两个节点，其中prev指向第一个节点，cur指向第二个节点。 接下来， 将prev的next指针指向cur的next节点，即将第一个节点的后继指针指向第三个节点。 然后，将cur的next指针指向prev，完成节点的交换。 接着, 递归地处理剩余部分的链表，即将第三个节点及其后面的节点作为参数传入swapPairs函数中，并获得返回的结果。 最后，将交换后的新头节点cur返回。

完整代码

class Solution(object):
    def swapPairs(self, head):
        # 检查当前链表是否为空或者只有一个节点
        if not head or not head.next:
            return head

        # 定义prev指针指向当前要交换的两个节点中的第一个节点
        prev = head
        # 定义cur指针指向当前要交换的两个节点中的第二个节点
        cur = head.next

        # 将prev的next指针指向cur的next节点
        prev.next = self.swapPairs(cur.next)
        # 将cur的next指针指向prev，完成节点的交换
        cur.next = prev

        # 返回交换后的链表的头节点
        return cur

详细分析

class Solution(object):
    def swapPairs(self, head):

这是定义了一个名为Solution的类，并声明了一个名为swapPairs的方法。该方法接受一个参数head，表示链表的头节点。

        # 检查当前链表是否为空或者只有一个节点
        if not head or not head.next:
            return head

在这里，首先检查链表是否为空或者只有一个节点。如果是，说明无需进行交换，直接返回原链表。

        # 定义prev指针指向当前要交换的两个节点中的第一个节点
        prev = head
        # 定义cur指针指向当前要交换的两个节点中的第二个节点
        cur = head.next

这两行代码定义了两个指针prev和cur，分别指向当前要交换的两个节点。prev指向第一个节点，cur指向第二个节点。

        # 将prev的next指针指向cur的next节点
        prev.next = self.swapPairs(cur.next)

这一行代码将prev的next指针指向cur的next节点，实现了节点的交换。同时，使用递归调用swapPairs方法来处理剩余部分的链表，并将返回的结果赋值给prev.next，即连接交换后的节点。

        # 将cur的next指针指向prev，完成节点的交换
        cur.next = prev

这一行代码将cur的next指针指向prev，完成了节点的交换。交换后，prev变为了第二个节点，cur变为了第一个节点。

        # 返回交换后的链表的头节点
        return cur

最后，返回交换后的链表的头节点cur。

整体思路是通过递归不断处理每一对节点进行交换，直到链表末尾或者只剩下一个节点。在每次递归中，首先交换当前两个节点，然后继续递归地处理剩余部分的链表。最终得到交换后的链表。

运行效果截图