《单链表的环的入口点一个小证明》

http://blog.csdn.net/learniting/article/details/7314475  中《单链表的环的入口点一个小证明》

 

如何判断一个单向链表是否有环？如果有，如何找到其入口节点的指针？

         算法思想：用两个指针p1,p2同时指向链表的头部，p1一次移动一步，p2一次移动两步，如果最终p1和p2重合则说明链表有环，如果p2走到空指针（链表的结尾）则说明链表无环； 如果最终p1和p2重合，使p2重新指向链表的头结点，然后p1和p2同时一次移动一步，当p1和p2再次重合时该节点指针就是环的入口节点指针

        可能有人问为什么会第二次会相遇呢

        首先如果单链表有环的话，必在尾端出现

       设单链表非环的部分为x个节点，环的部分为y个节点

       那么第一次当p1走入环的入口点即走了x步时，p2已经走了2x个节点，也就是在环的内部走了x个节点（ ny<x<(n+1)y)，那么p2所在的位置是 环的第(x-ny)个节点的位置，然后那么距环的入口的距离是y-(x-ny), 而此时p1在环的入口处,那么p2要追上p1这需要走y-(x-ny)步 

       而此时p1重新走，p2步伐也变为1 那么当p1走入入口时 p2也走了x步了 所以p2总共走了 2(x+y-(x-ny))+x=2(n+1)y+x个节点 我们可以想啊,p2是不是走了x步后然后在环中转了2(n+1)圈 所以p2此时是在环的入口点俄，同时p1也刚好走到环的入口点，所以说此时它们刚好在环的入口点相遇

 

也可以用hash，参考：

http://hawstein.com/posts/2.5.html