参考链接列表长度？

Question

编辑：我要找的术语叫做循环检测。感谢@dhke在评论中提到这一点。你知道吗

我试图找出一种更好的方法来处理索引列表，如果一个列表的引用中有一个循环，那么它的长度是多少。我有一个函数，但它传递下一个索引值和计数器。我一直在想办法，只要把列表传递到函数中就行了。它总是以索引0开始。你知道吗

给定一个列表，列表中的每个节点都引用其他节点的索引。我想得到的是链表的长度，而不是链表中的节点数。你知道吗

# This list would have a length of 4, index 0->1->3->6->0
four_links_list = [1,3,4,6,0,4,0]
two_links_list = [3,2,1,0]

def my_ideal_func(list):
    # Some better way to iterate over the list and count

def my_func(list, index, counter):
    # We're just starting out
    if index == 0 and counter == 0:
        counter += 1
        return my_func(list, list[index], counter)
    # Keep going through the list as long as we're not looping back around
    elif index != 0:
        counter += 1
        return my_func(list, list[index], counter)
    # Stop once we hit a node with an index reference of 0
    else:
        return counter

Answer 1

如果不需要额外的数据结构：

def tortoise_and_hare(l):
    tort = 0
    hare = 0
    count = 0
    while tort != hare or count == 0:
        count += 1
        if l[tort] == 0:
            return count
        tort = l[tort]
        hare = l[hare]
        hare = l[hare]
    return -1 

>>> tortoise_and_hare([1,3,4,6,0,4,0])
4
>>> tortoise_and_hare([3,2,1,0])
2
>>> tortoise_and_hare([1,2,3,1,2,1,2,1])
-1

Answer 2

不需要递归：

def link_len(l):
    cnt, idx = 0, 0
    while not cnt or idx:
        cnt = cnt + 1
        idx = l[idx]
    return cnt

这假设列表循环回0。你知道吗

Answer 3

您可以使用集合来跟踪您访问过的所有节点（集合具有非常快速的成员资格测试）。这里绝对不需要递归，循环可以很好地完成：

def my_ideal_func(list):
    visited_nodes= set()
    index= 0
    length= 0
    while True:
        node= list[index]

        if node in visited_nodes:
            return length

        visited_nodes.add(node)
        length+= 1
        index= list[index]