Floyd's Cycle Detect Algorithm: Remove Cycle (Loop) from a Linked List

Technology Community › Category: Linked Lists › Floyd’s Cycle Detect Algorithm: Remove Cycle (Loop) from a Linked List

VietMX Staff asked 4 years ago

Floyd’s cycle detect algorithm, also called the tortoise and hare algorithm as it involves using two pointers/references that move at different speeds, is one way of detecting the cycle. If there is a cycle, the two pointers (say slow and fast) will end up pointing to the same element after a finite number of steps. Interestingly, it can be proved that the element at which they meet will be the same distance to the start of the loop (continuing to traverse the list in the same, forward direction) as the start of the loop is to the head of the list. That is, if the linear part of the list has k elements, the two pointers will meet inside the loop of length m at a point m-k from the start of the loop or k elements to the ‘end’ of the loop (of course, it’s a loop so it has no ‘end’ – it’s just the ‘start’ once again). And that gives us a way to find the start of the loop:
Once a cycle has been detected, let fast remain pointing to the element where the loop for the step above terminated but reset slow so that it’s pointing back to the head of the list. Now, move each pointer one element at a time. Since fast began inside the loop, it will continue looping. After k steps (equal to the distance of the start of the loop from the head of the list), slow and fast will meet again. This will give you a reference to the start of the loop.
It is now easy to set slow (or fast) to point to the element starting the loop and traverse the loop until slow ends up pointing back to the starting element. At this point slow is referencing the ‘last’ element list and it’s next pointer can be set to null.

Implementation

public static LinkedListNode lastNodeOfTheLoop(LinkedListNode head) {
    LinkedListNode slow = head;
    LinkedListNode fast = head; 

    // find meeting point using Tortoise and Hare algorithm
    // this is just Floyd's cycle detection algorithm
    while (fast.next != null) { 
        slow = slow.next; 
        fast = fast.next.next; 
        if (slow == fast) { 
            break; 
        }
    }

    // Error check - there is no meeting point, and therefore no loop
    if (fast.next == null) {
        return null;
    }

    slow = head; 
    // Until both the references are one short of the common element which is the start of the loop
    while (slow.next != fast.next) { 
        slow = slow.next; 
        fast = fast.next; 
    }
    // Now fast points to the start of the loop (inside cycle).
    return fast;
}

LinkedListNode lastNodeOfTheLoop = findStartOfLoop(head);
lastNodeOfTheLoop.next = null; // or lastNodeOfTheLoop.next = head;

Question Tags: Linked Lists, Middle Level