链表中没环就返回NULL

有就返回环的入口

三种基本思路：

1、快慢指针找到环内的一个node，然后从链表头開始。对于每个node，看它在不在环中

2、用map存一下訪问过的节点地址，看当前node的地址是否在map中

3、事实上。经过计算，对于1中，快慢指针相遇的地方，再開始以慢指针開始走。

还有一方面，在链表的头部也用一个慢指针開始走，二者相遇的地方便是环的入口

（代码并未进行执行验证）

typedef struct node{	int data;	struct node * next;}listNode;

//find the first node in the cycle//1.step into the circle first and then for every node, take a loop to make sure//2.store the previous node and compare with the cunrrent node (what structure to store?)//3.after computation,while using slow and fast pointer,// we can get that a slow pointer at the begining and another one // at the encounter position will meet at the entrance of the cycle listNode *findFirstNodeInCycle1(listNode *pHead){	listNode *pFast=pHead;	listNode *pSlow=pHead;	while(pFast!=NULL&&pFast->next!=NULL)	{		pFast=pFast->next->next;		pSlow=pSlow->next;		if(pSlow==pFast)			break;	}	if(pFast==NULL||pFast->next==NULL)		return NULL;	//now the nodes are in the loop	//begin with the head	while(pHead)	{				pSlow=pSlow->next;		while(pSlow)		{			if(pSlow==pHead)				return pHead;			if(pSlow==pFast)				break;					pSlow=pSlow->next;		}		pHead=pHead->next;	}}//store in a map?

good or not? listNode *findFirstNodeInCycle2(listNode *pHead) { if(pHead==NULL) return; listNode *temp=pHead-next; map<int,char> storeMap; map[int(pHead)]=' '; while(teamp!=NULL&&storeMap.find(temp)==storeMap.end()) { storeMap[int(temp)]=' '; temp=temp->next; } return temp; } listNode *findFirstNodeInCycle3(listNode *pHead) { listNode *pFast=pHead; listNode *pSlow=pHead; while(pFast!=NULL&&pFast->next!=NULL) { pFast=pFast->next->next; pSlow=pSlow->next; if(pFast==pSlow) { listNode *pSlow2=pHead; while(pSlow2!=pSlow) { pSLow=pSlow->next; pSlow2=pSlow2->next; } return pSlow; } } return NULL; }