CTCI, 2.6.

/*02.01.2015
CTCI
2.6 Given a circular linked list, implement an algorithm which returns the node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points
to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A - > B - > C - > D - > E - > C [the same C as earlier]
Output: C*/

#include<stdio.h>
#include<iostream>

using namespace std;

class Node{
public:
    Node(int n){
        value = n;
    }
    int value;
    Node *next;
};


//solution: Floyd's cycle-finding algorithm,"tortoise and the hare algorithm". source: Wikipedia
Node *detectCycle(Node *head){
    Node *fast = head;
    Node *slow = head;

    while (1){
        if (!fast->next)
            return NULL; // we've reached the end - no cycle detected

        fast = fast->next;

        if (!fast->next)
            return NULL; // we've reached the end - no cycle detected

        fast = fast->next;
        slow = slow->next; // we moved fast by two, slow by one step

        if (fast == slow){
            //meeting point - cycle detected
            break;
        }
    }
    //fast and slow are at the meating point
    //move slow back to begining
    slow = head;
    while (1){
        slow = slow->next;
        fast = fast->next; //move each by one, when they meet again, it is beginning of the cycle
        if (slow == fast){
            return slow; // begining of cycle, return the node!
        }
    }

    return NULL;
}

int main(){
    Node *one = new Node(1);
    Node *two = new Node(2);
    Node *three = new Node(3);
    Node *four = new Node(4);
    Node *five = new Node(5);
    Node *six = new Node(6);

    one->next = two;
    two->next = three;
    three->next = four;
    four->next = five;
    five->next = six;
    six->next = two;

    Node *cycleStart = detectCycle(one);

    if (cycleStart)
        cout << cycleStart->value << "\n";

}