Cycle Detection

Floyd's Cycle Detection

• fast will enter the loop before slow
• The distance keeps on increasing by 1 in every iteration
• When distance becomes length of cycle they must meet

Python

def isLoop(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Remove cycle

Python

def removeLoop(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    if slow != fast:
        return
    slow = head
    while slow.next != fast.next:
        slow = slow.next
        fast = fast.next
    fast.next = None