Introduction

Floyd’s cycle finding algorithm or tortoise and hare algorithm finds cycles in a linked list. If there is a cycle in a linked list, a slow pointer can meet up with the fast pointer. An analogy would be that the slow tortoise has “caught up” with the fast hare.

Linked list with a cycle

p1 p2 slow fast

Let $a$ be the distance from the start node to the cycle start node, $b$ the distance from the cycle start node to the meet node and $T$ be the cycle length.

Slow pointer $p_1$ moves 1 node at each time step. Fast pointer $p_2$ moves 2 nodes at each time step.

  1. If there is no cycle, $p_2$ will reach the end(last) node first.
  2. If there is a cycle, both pointers meet at a node within the cycle.

Proof

\(\begin{aligned} Distance(p_1) &= a + b + k_1T\\ Distance(p_2) &= a + b + k_2T\\ Distance(p_2) &= 2Distance(p_1)\\ a + b + k_2T &= 2(a + b + k_1T)\\ a + b &= (k_2-2k_1)T\\ a &= (k_2-2k_1)T - b\\ a &= kT - b\\ &where \ k_1<k_2, k_1, k_2, k \in \mathbb{Z}^{+}\\ \end{aligned}\) Since $k$ is an non-negative integer, both pointers meet at a node within the cycle. Hence

Note that when both pointers meet, the fast pointer is $b$ steps ahead of the cycle start node. Hence, if the fast pointer advances $a$ steps forward, it will be at the cycle start node. If we reset the slow pointer to the start node, and advance both pointers 1 step at a time, both pointers will meet at the cycle start node.

Modulo arithmetic

Position of fast pointer (with respect to cycle index) is essentially \(\begin{aligned} (D-a) \ mod \ T\\ \end{aligned}\) Position of fast pointer (with respect to node index) is essentially \(\begin{aligned} a + (D-a) \ mod \ T\\ \end{aligned}\) where $D$ is the distance from start node, $a$ the distance from start node to the cycle start node, $T$ is the cycle period.

Code implementation

mutable struct Node
    index::Int32
    next_node::Union{Node, Nothing}
end

# linked list
linked_list = Node(0, Node(1, Node(2, Node(3, nothing))))

# cycle list
cycle_start = Node(2, nothing)
cycle = Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9, cycle_start)))))))
cycle_start.next_node = cycle
cycle_list =  Node(0, Node(1, cycle_start))

# floyd cycle finding algorithm
function floyd(start_node)
    p1 = start_node   # slow pointer
    p2 = p1   # fast pointer

    while true
        # checks if fast pointer reachs end of linked list
        if p2.next_node == nothing || p2.next_node.next_node == nothing
            println("No cycle")
            break
        end

        # advance fast and slow pointer
        p1 = p1.next_node
        p2 = p2.next_node.next_node
        println(p1.index,", ",p2.index)

        # if pointers meet, found meeting node
        if p1 == p2
            println("Meet node: ", p1.index)

            # find start of cycle
            p1 = cycle_list
            while (p1 != p2)
                p1 = p1.next_node
                p2 = p2.next_node
            end
            println("Cycle start node: ", p1.index)
            break
        end
    end
end
floyd(linked_list)
# Output:
#=
1, 2
No cycle 
=#
floyd(cycle_list)
# Output:
#=
1, 2
2, 4
3, 6
4, 8
5, 2
6, 4
7, 6
8, 8
Meet node: 8
Cycle start node: 2
=#
#include <iostream>
using namespace std;

struct Node{
    int index;
    Node* next;
};

void build_linked_list(Node* head, int n_nodes);
void build_cycle_list(Node* head, int a, int T);
void print_list(Node* node);
void floyd(Node* head);

int main(){
    // linked list
    Node* ll_head = new Node();
    ll_head -> index = 0;
    ll_head -> next = NULL;
    build_linked_list(ll_head, 10);
    cout<<"linked list:";
    print_list(ll_head);
    floyd(ll_head);
    cout<<endl;

    //cycle list
    Node* cycle_head = new Node();
        cycle_head -> index = 0;
        cycle_head -> next = NULL;
    build_cycle_list(cycle_head, 3, 6);
    floyd(cycle_head);
    return 0;
}

void build_linked_list(Node* head, int n_nodes){
    Node* ptr = head;
    for (int i=1; i<=n_nodes; i++){
        Node* node = new Node();
            node -> index = i;
            node -> next = NULL;
        ptr -> next = node;
        ptr = node;
    }
}

void build_cycle_list(Node* head, int a, int T){
    Node* ptr = head;
    for (int i=1; i<a+T; i++){
        Node* node = new Node();
            node -> index = i;
            node -> next = NULL;
        ptr -> next = node;
        ptr = node;
    }
    Node* ptr2 = head;
    for (int i=0; i<a; i++){
        ptr2 = ptr2 -> next;
    }
    ptr -> next = ptr2;
}

void print_list(Node* node){
    while (node -> next!=NULL){
        cout<<node -> index;
        node = node -> next;
    }
    cout<<endl;
}

void floyd(Node* head){
    Node* p1 = head; //slow pointer
    Node* p2 = p1;   //fast pointer
    while (p2 -> next != NULL){
        if (p2 -> next -> next != NULL){
            p1 = p1 -> next;
            p2 = p2 -> next -> next;
            cout<<p1 -> index<<","<<p2 -> index<<endl;
            if (p1 == p2){
                cout<<"Meet node: "<<p1 -> index<<endl;
                //find start of cycle
                p1 = head;
                while (p1 != p2){
                    p1 = p1 -> next;
                    p2 = p2 -> next;
                }
                cout<<"Cycle start node: "<<p1 -> index<<endl;
                return;
            }
        }
    }
    cout<<"no cycle"<<endl;
}
// Output
linked list:0123456789
1,2
2,4
3,6
4,8
5,10
no cycle

1,2
2,4
3,6
4,8
5,4
6,6
Meet node: 6
Cycle start node: 3

Interactive Demo

1

1

References

  1. https://cp-algorithms.com/others/tortoise_and_hare.html