Detecting a cycle in a singly linked list

Idea to detect a cycle in a singly linked list is a below.

  • Traverse the linked list from the head node and store the nodes in a set as they are visited. Every time a node is visited, check if it exists in the set; if it does then a cycle is detected.

Time Complexity : O ( N ), where N is the number of nodes in the linked list.
Space Complexity : O ( N ), where N is the number of nodes in the linked list.



C++ program to detect a cycle in a singly linked list.

#include<iostream>
#include<set>

using namespace std;

class Node {

    public:
    int data;
    Node* next;
    Node (int arg_data) : data (arg_data), next (nullptr)
    {}
};

class SingleLinkedList {

    public:

    SingleLinkedList()
    {}

    // Detect cycle returns a node where the cycle beings.
    // If no cycle is found, a nullptr is returned.

    Node* Detect_Cycle (Node *head) {

        set<Node*> set_nodes;

        while (head != nullptr) {

            if (set_nodes.find(head) == set_nodes.end()) {
                set_nodes.insert(head);
                head = head->next;
            } else {
                return head;
            }
        }
        return nullptr;
    }

    // Free the linked list

    void Free (Node *head) {

        std :: cout << "Freeing node in the linked list.";

         set <Node *> deleted_nodes;

         while (head != nullptr && deleted_nodes.find(head) == deleted_nodes.end()) {
             Node * temp = head->next;
             head->next = nullptr;
             delete head;
             deleted_nodes.insert(head);
             head = temp;
         }
    }
};

int main() {

    Node *head   = new Node(2);
    Node *node_3 = new Node(3);
    Node *node_5 = new Node(5);
    Node *node_7 = new Node(7);
    Node *node_13 = new Node(13);

    head->next = node_3;
    node_3->next = node_5;
    node_5->next = node_7;
    node_7->next = node_13;
    node_13->next = node_5;

    SingleLinkedList s;

    Node * tmp = s.Detect_Cycle(head);
    if (tmp) {
        std :: cout << "Cycle begins at node : " << tmp->data << std :: endl;
    } else {
        std :: cout << "No cycle detected." << std :: endl;
    }

    s.Free(head);

    return 0;
}

Output

Cycle begins at node : 5
Freeing node in the linked list.


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.