带链表的尾循环拼图 - 当尾长于循环时，我的 Python 解决方案失败

Question

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

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

基本上，输入是 linked 列表的第一个节点，它保证有一定长度的尾部和一定长度的循环。（图片见 link。）

我的解决方案是让两个迭代器遍历列表，一个访问每个节点，一个跳过每个节点。一旦它们命中，我就知道我在循环中，所以我只计算一个循环，然后 return 计数。

这是我的代码：

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

带链表的尾循环拼图 - 当尾长于循环时，我的 Python 解决方案失败

Tail-Loop Puzzle with a Linked list - My Python solution is Failing when tail is longer than loop

python

loops

linked-list

singly-linked-list