为什么我的linkedlist中有一个循环，即使它被编码为提前退出？

Question

我正在编写代码来解决以下链表问题： https://leetcode.com/problems/swap-nodes-in-pairs/

总而言之，交换链表中的相邻节点是一种方法

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return []
        
        prev= head
        nex=head
        connector= None
        output = head.next
        count = 0 

        while prev:
            curr = nex.next
            if count>=1: 
                connector.next = curr  
            nex = curr.next
            curr.next = prev
            connector = prev
            prev=nex
            count +=1
        
        return output

如果我运行input [1,2,3,4]，我会得到一个Error - Found cycle in the ListNode。然而，当我用这个输入在纸上运行上面的代码时，它就像一个符咒！并在应该的时候退出-没有循环。你知道这个所谓的周期发生在哪里吗

Answer 1

对于这个问题，你保持的状态比你需要的要多。例如，count是完全不必要的。您所需要的不是检查count >= 1，而是检查connector is not None。从一个迭代到下一个迭代，您真正需要的唯一状态是要交换的下一个节点，可能还有它的后续节点（作为一种优化，以避免必须多次获取它）

关于创建循环的特定错误，考虑循环的第一次迭代。在循环的顶部，nex等于head，因此nex引用列表中的第一个节点

然后设置curr = next.next，以便curr引用列表中的第二个节点（如果没有第二个节点，则为None）。然后设置nex = curr.next，因此nex现在引用列表中的第三个节点（或者None，如果没有第三个节点）。但这里有一只虫子。如果curr是None怎么办？那么curr.next将导致错误，对吗？所以这需要修正

但是假设列表至少有两个节点，此时我们有curr引用第二个节点和nex引用第三个节点（如果有）。列表本身尚未更改

它现在设置curr.next = prev。由于curr是第二个节点，prev仍然是第一个节点，因此它将第二个节点的后续节点设置为第一个节点。它现在创建了一个循环：第一个节点的后续节点现在是第二个节点，第二个节点的后续节点现在是第一个节点。第三个节点（如果有）不再被列表引用。换句话说，它没有交换前两个节点。它只是在它们之间创造了一个循环

在这一点上，它几乎脱离了轨道。提示：交换两个节点需要更改三个next属性：最初引用对中第一个节点的属性需要更改为引用第二个，对中第一个节点的next属性需要更改为第二个节点的next属性，以及next需要更改第二个节点的属性以引用第一个节点。之后，第一个节点将成为第二个节点，第二个节点将成为第一个节点：

... A -> first -> second -> B ...

变成：

... A -> second -> first -> B ...

所以A.next需要改变，first.next需要改变，second.next需要改变。不需要对B进行任何更改

我建议仔细检查逻辑，仔细地，看看当有0，1，2，3。。。列表中的节点。您将立即发现问题，这些问题经识别后可以修复

更新：这里有一个完整的解决方案（只有Solution被更改）：

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr and curr.next:
            next = curr.next

            if prev is None:
                head = next
            else:
                prev.next = next

            curr.next = next.next
            next.next = curr

            prev = curr
            curr = curr.next

        return head

请注意，循环中的每个迭代都会通过两个列表节点。循环末尾的两个更新设置了prev和curr，它们使用的是更新的curr节点，它现在是当前对中的第二个节点