本文共 884 字，大约阅读时间需要 2 分钟。

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]

output: C

分析：这也是一道链表的经常讨论的题目。有些题目是判断链表中是否有环？方法是使用一个快指针，一个慢指针，两者必定相遇；有些题目是判断链表是否相交，这个的解法就比较多。

我开始确实也没有想明白，研究了一下答案。如果A表示慢指针、B表示快指针，当A到达环入口点的时候，假设B领先A k个位置，则他们相遇的地方一定距离入口点k个位置。因为如果A、B同在起始点，则相遇点也在起始点。B领先k个位置，则相遇点距离起点点反方向k个位置。

代码：

Node* find_loop_start(Node* head){	if(head==NULL) return;	Node* fast=head,*slow=head;	while(1){		slow=slow->next;		fast=fast->next;		if(fast!=NULL){			fast=fast->next;			if(fast==slow)				break;		}		else			break;	}	if(fast==NULL)		return NULL;	slow=head;	while(1){		if(slow==fast)			return fast;		slow=slow->next;		fast=fast->next;	}}

转载地址：http://dbyab.baihongyu.com/