LeetCode24 两两交换链表节点 递归Python实现输出错误排查

核心问题 #

你的代码中多余的while循环是导致输出错误的根本原因，递归实现两两交换链表节点不需要迭代循环，多余的循环会重复修改节点指针，破坏已经构建好的链表结构。

错误执行逻辑（以输入N1->N2->N3->N4为例） #

• 首次调用函数传入头节点N1，满足while判断条件，初始化p1=N1、p2=N2，执行p1.next = self.swapPairs(p2.next)即调用函数处理N3开头的子链表
• 子链表调用中同样进入while循环，初始化p1=N3、p2=N4，执行p1.next = self.swapPairs(None)返回None，p2.next = N3，此时子链表while再次判断head=N3的next已经是None，退出循环返回p2=N4
• 回到外层函数，此时head=N1的next已经被赋值为N4，仍然满足while判断条件，会再次执行p1=N1、p2=N4，重写指针将p2的next指向N1，最终循环结束返回最后一次赋值的p2，链表结构被篡改得到错误输出。

修复方案 #

直接删除多余的while循环即可，修正后代码如下：

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 终止条件：没有节点或只剩一个节点，不需要交换
        if head == None or head.next == None:
            return head
        p1,p2 = head, head.next
        # 第一个节点的next指向后续子链表交换后的头节点
        p1.next = self.swapPairs(p2.next)
        # 第二个节点的next指向第一个节点完成交换
        p2.next = p1
        # 返回当前组交换后的头节点
        return p2

修正后代码的递归逻辑完全符合题目要求，输入N1->N2->N3->N4时会正确返回N2->N1->N4->N3。

内容的提问来源于stack exchange，提问作者yining wang