带有链表的尾循环难题 - 当尾巴比循环长时，我的 Python 解决方案失败

Question

我一直在研究一个关于代码战争的谜题，可以在这里找到：

http://www.codewars.com/kata/can-you-get-the-loop

基本上，输入是链表的第一个节点，它保证有一个一定长度的尾巴和一个一定长度的循环。（有关图片，请参阅链接。

我的解决方案是让两个迭代器遍历列表，一个访问每个节点，另一个跳过每个节点。 一旦他们命中，我知道我在循环内，所以我只计算一个周期并返回计数。

这是我的代码：

def loop_size(node):
    size = 1
    onestep = node
    twostep = node.next
    while(onestep != twostep):
        twostep = twostep.next.next
        onestep = onestep.next
    #we are inside the loop
    #onestep == twostep
    onestep = node.next
    size += 1
    while(onestep != twostep):
        size += 1
        onestep = onestep.next
    return size

出于某种原因，我得到了奇怪的结果。 每当尾巴小于循环时，我都会得到正确的结果。 但是每当尾巴长于或等于循环的大小时，我的函数就会获得更高的计数。

以下是一些示例：

Tail length = 1 Loop Length = 3
###result 3 - correct
Tail length = 999 Loop Length = 1000
###result 1000 - correct
Tail length = 1000 Loop Length = 999
###result 1998 - incorrect
Tail length = 50 Loop Length = 3
###result 51 - incorrect
Tail length = 3 Loop Length = 3
###result 6 - incorrect
Tail length = 3 Loop Length = 4
###result 4 - correct

Answer 1

行

onestep = node.next

应该是

onestep = onestep.next

否则，您将再次从头部开始并重新进入循环，因此您的结果将是尾部长度太长。 另外，我相信您的大小应该以 1 开头，而不是像您拥有的那样以 2 开头（大小 = 1，大小 += 1 在第二个循环开始之前）。

此代码适用于所有示例：

class Node(object):
    def __init__(self, next_node=None):
        self.next_node = next_node
    @property
    def next(self):
        return self.next_node
    def set_next(self, new_next):
        self.next_node = new_next
        return new_next
def loop_size(node):
    onestep = node
    twostep = node.next
    while(onestep != twostep):
        twostep = twostep.next.next
        onestep = onestep.next
    onestep = onestep.next
    size = 1
    while(onestep != twostep):
        size += 1
        onestep = onestep.next
    return size
def test_ll(tail, loop):
    head = Node()
    nodes = [head]
    for i in range(2, tail+loop+1):
        head = head.set_next(Node())
        nodes.append(head)
    nodes[-1].set_next(nodes[tail])
    size = loop_size(nodes[0])
    print "Tail: {}, Loop: {}, Size: {}".format(tail, loop, size)
test_ll(1, 3)
test_ll(999, 1000)
test_ll(1000, 999)
test_ll(50, 3)
test_ll(3, 3)
test_ll(3, 4)

输出

Tail: 1, Loop: 3, Size: 3
Tail: 999, Loop: 1000, Size: 1000
Tail: 1000, Loop: 999, Size: 999
Tail: 50, Loop: 3, Size: 3
Tail: 3, Loop: 3, Size: 3
Tail: 3, Loop: 4, Size: 4