Java资源分享网 - 专业的Java学习网站 学Java,上Java资源分享网
代码随想录知识星球精华(最强八股文)第五版(算法篇) PDF 下载
发布于:2024-03-01 10:12:15
(假如点击没反应,多刷新两次就OK!)

代码随想录知识星球精华(最强八股文)第五版(算法篇) PDF 下载  图1

 

 

资料内容:

 

环形链表

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步