find_cycles_in_list.cpp

find_cycles_in_list.cpp

#include <iostream>
#include <set>

struct node{
    int id;
    node* next;
};


void func ( node* head )
{
    node *cur = head;
    std::set<node*> c;
    while (cur->next != NULL)
    {
        if ( c.find( cur->next ) == c.end() )
        {
            c.insert( cur );
        }
        else
        {
            std::cout << cur->id;
            return;
        }
        cur = cur->next;
    }
    std::cout << "no cycles";
}

void func2 ( node* head ){
    node *cur1 = head->next;
    node *cur2 = head->next->next;


    while ( cur1 != cur2 && cur2->next != NULL && cur2->next->next != NULL )
    {
        cur1 = cur1->next;
        cur2 = cur2->next->next;
    }

    if ( cur1 == cur2 )
        std::cout<< cur1->id;
    else
        std::cout << "no cycles";
}

void pr( node* head )
{
    while ( head != NULL )
    {
        std::cout << head->id;
        head = head->next;
    }
    std::cout << std::endl;
}

int main ()
{
    node* head = new node();
    head->id = 1;
    head->next = new node();
    node* cur = head->next;
    cur->id = 2;
    cur->next = new node();
    cur = cur->next;
    cur->id = 3;
    cur->next = new node();
    cur = cur->next;
    cur->id = 4;
    cur->next = new node();
    cur = cur->next;
    cur->id = 5;
    cur->next = head->next;
    //pr(head);
    func2( head );
    func( head );
    return 0;
}