这题的思想来自于http://hawstein.com/posts/2.5.html，重新实现了一下

用hash来记录循环的起点

//Given a circular linked list, implement an algorithm which returns 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]

#include <iostream>

#include <map>

using namespace std;

typedef struct node{

	int data;

	node *next;

}node;

node* init(int a[], int n, int m){

	node *head, *p, *q;

	for(int i=0; i<n; ++i){

		node *nd = new node();

		nd->data = a[i];

		if(i==m) q = nd;

		if(i==0){

			head = p = nd;

			continue;

		}

		p->next = nd;

		p = nd;

	}

	p->next = q;

	return head;

}

map<node *, bool> st;

node * getLoopStart(node *head)

{

	node *p =head->next;

	while(p)

	{

		if (st[p] != true)

		{

			st[p] = true;

			p=p->next;

		}

		else

			return p;

	}

	return p;

}

int main(){

	int n = 10, m = 9;// m<n

	int a[] =

	{

		3, 2, 1, 3, 5, 6, 2, 6, 3, 1

	};

	node *head = init(a, n, m);

	//node *p = loopstart(head);

	node *p2 = getLoopStart(head);

	if(p2)

		cout<<p2->data<<endl;

	return 0;

}