BiscuitBoy
2022-11-08 12:34 电子科技大学 Java
关注
快慢指针原理说明：1.单向链表中如果有环，一定是最后一个结点的后继指针又指向了已遍历结点（这个已遍历结点可以称为三叉结点，因为该结点有两个入口一个出口），从而形成环。2.因为有环的存在，所以以后继结点非空为条件进行的遍历永远不会停止。3.当慢指针首次到达三叉结点，也就是慢指针开始进入环中时，快指针可能位于环中任一结点处：快指针可能落后慢指针0个结点（快慢指针均位于三叉结点，即刚好相遇）、落后1个结点、2个结点、3个等等，最多落后L-1个节点（L是环中结点总数，即快指针恰位于慢指针的后继结点处）。由于快指针每一跳都比慢指针多前进一个位置，因此，快指针最多也只需要L-1跳就追上慢指针（相遇）。如果是L-1跳后两指针才首次相遇，此时，慢指针刚好来到链表最后一个结点（三叉结点的前驱结点）。因此可以断言：快慢指针首次相遇时，慢指针走过的距离不超过链表的总长度。ps：纯文字描述可能难以理解，可以画图辅助，将三叉结点标记为L号结点，画一个包含L个结点的环即可。
4
相关推荐
点赞 评论 收藏
分享
02-10 10:11
门头沟学院 前端工程师 
钱嘛数字而已：
辅导员肯定不能同意，不然你出事了，他要承担责任。但是，脚和脑子都长在你自己身上，使用它还需要向辅导员报告么？
辅导员必须按流程拒绝你，然后你拿出成年人的态度，做自己的选择。 点赞 评论 收藏
分享
02-09 20:12
门头沟学院 测试开发 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 牛客新年AI问运 #
3155次浏览 77人参与
# 刚工作，应该先搞钱or搞成长？ #
20840次浏览 159人参与
# 牛客AI体验站 #
15607次浏览 277人参与
# 你觉得第一学历对求职有影响吗？ #
229983次浏览 1266人参与
# 如何提高实习转正率？ #
85666次浏览 503人参与
# 找工作中的小确幸 #
80399次浏览 448人参与
# 实习在多还是在精 #
82789次浏览 509人参与
# 你觉得技术面多长时间合理？ #
168106次浏览 1170人参与
# 牛友的春节生活 #
11830次浏览 229人参与
# 月薪多少能在一线城市生存 #
136413次浏览 898人参与
# 选了这个offer，你有没有后悔？ #
738544次浏览 4472人参与
# 备战春招/暑实，现在应该做什么？ #
7907次浏览 204人参与
# 从夯到拉，锐评职场mentor #
7744次浏览 113人参与
# 实习到现在，你最困惑的一个问题 #
6924次浏览 169人参与
# 电网笔面经互助 #
59688次浏览 476人参与
# 找工作中的意难平 #
983408次浏览 6424人参与
# 制造业的秋招小结 #
143361次浏览 2089人参与
# 春招什么时候投？ #
13205次浏览 209人参与
# 秋招踩过的“雷”，希望你别再踩 #
185690次浏览 1684人参与
# 你有哪些缓解焦虑的方法？ #
51164次浏览 906人参与