Cycle Detection

For the following linked list

1. How to tell whether a linked list contains such a loop ?

2. How to find where the loop starts and break it there to “fix” the list ?

Tortoise and Hare

It is called the tortoise-and-hare algorithm or Floyd's cycle-finding algorithm after Robert Floyd.

The algorithm starts two objects called tortoise and hare moving through the list at different speeds starting at the beginning of the list.

• The tortoise moves one cell per step.

• The hare moves two cells per step.

If the two meet at the same node, it indicates that there is a cycle present in the linked list.

How we can detect the first node of the cycle ?

The following pseudocode shows the algorithm at a high level:

1. Start the tortoise moving through the list at one cell per step.

2. Start the hare moving through the list at two cells per step.

3. If the hare finds a null link, then the list has no loop, so stop.

4. Otherwise, when the hare catches the tortoise,

   Restart the hare at the beginning of the list, moving one cell per step this time.

   Continue moving the tortoise at one cell per step.

5. When the tortoise and hare meet again, they are at the start of the loop.

6. Leave the hare at the loop's starting point to take a well-deserved rest while the tortoise takes one more lap around the loop.

7. When the tortoise's Next pointer gives the cell where the hare is waiting, the tortoise is at the end of the loop.

8. To break the loop, set the tortoise's cell's Next pointer to null.

Marking Cells

Easiest way to tell whether a linked list has a loop is to traverse its cells, marking each as you visit it. If on a cell that is already marked, know that the list has a loop and that it starts at that point.

Node findLoopStart(Node head) {
    Node previous = null, current = head;
    while(current != null) {
        if(current.visited) {
          // can use previous to break the loop
          return current;
        }
        previous = current;
        current = current.next;
    }
    
    return null;
}

This algorithm also requires that each cell have an added Visited field.

Using Hash Tables

Move through the list, adding each cell to a hash table.

• On visiting a node checks the hash table to see whether the node is already in the table.

• If it comes to a node that is already in the hash table, the list contains a loop that starts at that node.

This algorithm obeys the restriction that we are not allowed to modify the node class, but it uses extra storage

Loops in Doubly Linked Lists

If there is a loop, somewhere a Next pointer jumps back to an earlier part of the list

The Prev pointer in that cell points to an earlier cell, not the one that created the loop.

References

• Floyd's Linked List Cycle Finding Algorithm