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?