#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;
}