带有两个指针的链表试图捕获循环

Question

您好，我需要有关检测循环和在链接列表上返回False的帮助，但首先，让我解释一下这个链接列表的外观：

这将是节点类：

class Node:

        def __init__(self, next = None, stairs = None):
            self.next = next
            self.stairs = stairs

Answer 1

因为你的步长不会改变代码，一旦它访问了一个节点两次，就会一遍又一遍地访问它。这是因为它将在重复节点之后的每个节点上做出相同的决定。因此，您只需要检测是否（至少）有一个节点被访问了两次。两种常见的方法是：

1. 计算链表中有多少节点（例如，取一个新变量N=0，并在每次运行play函数的第一个循环时递增它）。然后在第二个循环中计算访问了多少个节点。一旦这个数字大于N，您就知道至少有一个节点被访问了至少两次，因此您检测到一个圆，需要break退出循环（或return）。在

def play(first, step):
    '''(LinkedList, int) -> bool
    '''
    # locates the end_node
    end_list = first
    found = False
    # Used to find Node population
    N = 0
    while end_list.next != None and found != True:
        if end_list.next == first:
            found = True
        else:
            end_list = end_list.next
        N = N + 1
    stepcount = 1
    count = 1
    current = first
    winner = False
    loop = False
    # Goes through the linked list
    while current != None and winner != True and loop != True:

        # If count == step, then we check if we are at the last square or  
        # else if we are on a stairs then we may use them. 
        # If none of them are found then we itterate normally making count back to 1.
        # If stepcount passes the overall N (population of all the nodes),     then it will detect a loop

        if stepcount > N:
            loop = True #one node has been visited more than once so there is a loop
        elif count == step:
            if current == end_list:
                winner = True
            elif current.stairs:
                current = current.stairs
                count = 0
            else:
                current = current.next
                count = 0
            stepcount = stepcount + 1
        else:
            current = current.next
            count = count + 1
    return current == end_list

1. 跟踪您访问过的节点：要做到这一点，您只需向您访问的每个节点添加一个新属性（即node.visited = True）。在函数play的开始（即在初始循环中），您需要确保结构是干净的，即set node.visited = False。如果您不想在函数play被调用后更改节点，那么可以在末尾的另一个循环中删除它们（即del node.visited）。在

Answer 2

可能性：

1. 使用某种类型的节点或路径禁用，就像我上次建议的那样。你的帖子没有提到为什么这对你无效。在
2. 计算您已经采取了多少步骤，并与节点总体进行比较（称之为N）。如果你不走到终点就走了n步，那么你就陷入了一个循环。在
3. 尝试构建一个新列表，其中包含从开始到最终节点的步骤。这是一个严格的线性链接列表，例如START->；3->；6或START->；1->；2->；3。。。如果你试图添加一个已经在这个链接列表中的节点，那么你就有了一个循环。在