Linked List Detect A Cycle

Slow and Fast Pointer

Posted by Micah on October 31, 2018



C++ solution. Use slow and fast pointer, during the traversal, slow pointer takes one step and fast takes two steps. If there is a cycle in the list, the fast pointer will equal to slow pointer. Otherwise, fast pointer will reach the tail first.

C++ Solution

bool has_cycle(Node* head) {

    if(head == NULL || head->next == NULL){
        return false;

    Node* slow = head;
    Node* fast = head->next;

    while(slow != fast){
        if(fast == NULL || fast->next == NULL) return false;
        slow = slow->next;
        fast = fast->next->next;

    return true;