资料内容:
环形链表
1、先要判断是否有环
判断是否有环,这个在环形链表l当中使用fast指针每次移动两个结点和slow指针每次移动一个结点当两者相等时表示有环。
(fast相对slow指针相对运动,每次接近一个结点,直到重合,所以fast不会错过slow)
2、再找出环的入口位置
环的入口位置,新建一个指针从head开始移动和slow指针一起,每次移动一格,两者相遇结点即为环入口结点证明:
设链表长度为a + b,a为环入口距离(不包括链表入口结点),b为环长度,f为fast指针,s为slow指针f=2s(快指针每次2步,路程刚好2倍)
f= s+ nb(相遇时, fast刚好多走了n圈)推出相遇时slow指针走了: s =nb
从head结点走到入环点需要走∶a + nb,而slow已经走了nb,那么slow再走a步就是入环点了所以,从head开始,和slow指针一起走,相遇时刚好就是a步