How to detect a cycle in a linked list ?

  • A linked list is said to contain a cycle if any node is visited more than once.
How do you detect a cycle in a linked list

Method 1 – Using Hashing

  • Traverse the given list.
  • Insert each encountered node into a hash table.
  • If the current already present ,that means the cycle is present or not.

Sample code

#include <iostream>
#include <unordered_set>
using namespace std;

// Data Structure to store a linked list node
struct Node
{
    int dt;
    Node* next;
};

// Helper function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int dt)
{
    // create a new linked list node from heap
    Node* newNode = new Node;

    newNode->dt = dt;
    newNode->next = headRef;
    headRef = newNode;
}

// Function to detect Cycle in a linked list using Hashing
bool detectcyc(Node *head)
{
    Node *current = head;
    unordered_set<Node*> set;

    // traverse the list
    while (current)
    {
        // return false if we already have seen this node before
        if (set.find(current) != set.end())
            return true;

        // insert current node into the set
        set.insert(current);

        // move to the next node
        current = current->next;
    }

    // we reach here if list does not contain any cycle
    return false;
}

// Detect Cycle in a linked list
int main()
{
    // input keys
    int k[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(k) / sizeof(k[0]);

    Node* head = nullptr;
    for (int i = n - 1; i >= 0; i--)
        push(head, k[i]);

    // insert cycle
    head->next->next->next->next->next = head->next->next;

    if (detectcyc(head))
        cout << "Cycle Found";
    else
        cout << "No Cycle Found";

    return 0;
}

Output

Cycle Found

Method 2 – Floyd’s Cycle Detection Algorithm

  • Use two pointers, which move through the sequence at different speed.
  • The fast pointer moves twice as quickly as the slow pointer.
  • Here the distance between the two pointers increased by 1 at each step.
  • If these pointers meet at same node then there is a loop else linked list doesn’t have loop.

Sample Code

#include <iostream>
#include <unordered_set>
using namespace std;

// Data Structure to store a linked list node
struct Node
{
    int dt;
    Node* next;
};

// Helper function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int dt)
{
    // create a new linked list node from heap
    Node* nNode = new Node;

    nNode->dt = dt;
    nNode->next = headRef;
    headRef = nNode;
}

// Function to detect Cycle in a linked list using
// Floyd’s Cycle Detection Algorithm
bool dcycle(Node *head)
{
    // take two pointers - slow and fast
    Node *slow = head, *fast = head;

    while (fast && fast->next)
    {
        // move slow by one pointer
        slow = slow->next;

        // move fast by two pointers
        fast = fast->next->next;

        // if they meet any any node, linked list contains a cycle
        if (slow == fast)
            return true;
    }

    // we reach here if slow & fast pointer do not meet
    return false;
}

// Detect Cycle in a linked list using Floyd’s Cycle Detection Algorithm
int main()
{
    // input keys
    int k[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(k) / sizeof(k[0]);

    Node* head = nullptr;
    for (int i = n - 1; i >= 0; i--)
        push(head, k[i]);

    // insert cycle
    head->next->next->next->next->next = head->next->next;

    if (dcycle(head))
        cout << "Cycle Found";
    else
        cout << "No Cycle Found";

    return 0;
}

Output

Cycle Found

Categorized in:

Data Structure

Tagged in:

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,