求有环链表的环的起始节点

题目
求有环链表环上的第一个节点，即环的起始点。

这个问题其实是分为两部分的
（1）判断一个链表是不是有循环链存在。

我们可以设置两个指针fast,flow 。
fast是每次向下移动两个节点，low是每次向下移动一个节点。如果有循环链表他们必然会相遇。这个很好证明了。
首先如果如果有循环链表的话，这个两个指针都会进入循环链，在循环链中fast跑得比low快一个节点单位，所以肯定会追上它，那就一定会出现两个指针的值相等的情况。
代码如下：

 bool if_exist(Node* head){Node *fast,*low;fast=low=head;if(head==NULL||head->next==NULL||head->next->next==NULL)return false;while(fast!=NULL&&low!=NULL&&fast->next!=NULL){fast=fast->next->next;low=low->next;if(fast==low)return true;}return false;}

没什么难的，接下来这个问题就有点难度了
（2）求循环链表的第一个公共节点，这个用到一部分上述结论，先说方法吧，我们找到那个公共节点后，将一个指针先指向头结点，然后两个指针一起向下走，每次都只走一个节点，这样他们相遇的第一个节点就肯定是循环链的第一个公共节点！

推理
设环的长度为c(即m+l）,
fast走的路程:s+cround1+m
low走的路程:s+cround2+m;
fast路程是low路程的两倍，所以得出
s=c(2round1-round2)-m;
=c(2round1-round2-1)+c-m;
=c(2round1-round2-1)+I；

我们由此得到了结论
起点到环入口点s和相遇点到环路口点I的等式关系。
这个等式关系就充分说明了当指针low链表头开始，指针fast从相遇点开始，同时以一个步长往下走，必然会在第一个公共点相遇，当然，式子告诉我们可能fast先绕着环转个几圈再和low相遇。

代码

 Node* EntryNodeOfLoop(Node* head){if(head==NULL|| head->next==NULL|| head->next->next==NULL)return NULL;Node *p,*q;p = q=  pHead;while(p !=NULL && q!=NULL){p=p->next->next;q=q->next;if(p==q)break;}q=head;while(p != q){p=p->next;q=q->next;}return p;    }

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！