How to detect cycle in a linked list ?

Companies:
  • Adobe Interview Questions

How to find cycle in a linked list ?

There are multiple ways to find cycle in a linked list. However, the most common way to find cycle in a linked list is using Floyd’s cycle detection algorithm This algorithm is also known as the hare and tortoise algorithm, since it uses two pointers one of which is slow and one of which is fast.

Algorithm

Step 1: Initialize two pointers one fast_pointer, and one slow_pointer to the start of the linked list.
Step 2: While slow_pointer does not reach the end do the following :
Step 3: Move slow_pointer by one step and fast_pointer by two steps
Step 4: If slow_pointer and fast_pointer meet anywhere, it means that there is a cycle in the linked list.

If the slow_pointer reaches the end, and slow_pointer and fast_pointer do not meet ever, it means that there is no cycle in the linked list.

See the flowchart below for the steps:
FlowChart

Implementation

// C++ Program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
class Node {
    public:
    int data;
    Node* next;
};

void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new Node();

    /* put in the data */
    new_node->data = new_data;

    /* link the old list off the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

int findLoop(Node* list)
{
    Node *slow_pointer = list, *fast_pointer = list;

    while (slow_pointer && fast_pointer && fast_pointer->next) {
        slow_pointer = slow_pointer->next;
        fast_pointer = fast_pointer->next->next;
        if (slow_pointer == fast_pointer) {
            cout << "Found Loop";
            return 1;
        }
    }
    return 0;
}

int main()
{
    /* Start with the empty list */
    Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;
    detectloop(head);

    return 0;
}
Scroll to Top