LF4 - 2 months ago 7x
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

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
``````

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