Length of Cycle in Linkedlist
https://www.codewars.com/kata/52a89c2ea8ddc5547a000863/train/python
Reference: https://www.geeksforgeeks.org/find-length-of-loop-in-linked-list/
先让slow 和 fast 在cycle里面碰面。碰面后,让slow自己走完cycle重新遇见fast 这就得到长度。
def loop_size(node):
if node == None:
return 0
slow = node
fast = node
flag = 0
while slow and slow.next and fast and fast.next and fast.next.next:
if slow == fast and flag == 1:
cnt = 1
slow = slow.next
while slow != fast:
slow = slow.next
cnt+=1
return cnt
slow = slow.next
fast = fast.next.next
flag = 1
return 0
Last updated
Was this helpful?