LF4 LF4 - 1 year ago 103
Python Question

Reference Link List Length Python?

EDIT: The terminology I was looking for was is called Cycle Detection. Thanks to @dhke for referring that in the comments.

I'm trying to figure out a better way to process a list of indexes and what it's length is if a list has a loop in its reference. I have a function that works but it passes the next index value and counter. I've been trying to figure out a way to do it by just passing the list into the function. It always starts as index 0.

Given a list, each node in the list references the index of some other node. I'm trying to get the length of the linked list not the number of nodes in the list.

# 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
return counter

Answer Source

If you don't want extra data structures:

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])
>>> tortoise_and_hare([3,2,1,0])
>>> tortoise_and_hare([1,2,3,1,2,1,2,1])