Ссылка Ссылка Список Длина Python?

Question

EDIT: Терминология, которую я искал, называется Cycle Detection. Благодаря @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 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] 

Answer 3

Там нет необходимости рекурсии:

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

Это предполагает список возвращается к 0.