有环单链表的入口点/相遇点/环的长度

2017-03-29 19:26 阅读 678 次 评论 0 条

单链表作为最基本的数据结构,一直广受各大公司青睐,面试笔试题也是层出不穷,索性今天就写一篇关于单链表带环的文章,方便自己以及大家的学习。

如何判断单链表带环

我们可以通过定义两个指针的方法来实现,一个快指针,一个慢指针,两者都指向链表的头部,快指针pFast一次走两步,慢指针一次走一步,如果链表存在环,那么快指针pFast必然先进入环,而慢指针pSlow后进入环,两个指针必定相遇,当然,如果快指针pFast走到链表尾部依旧未与pSlow相遇,则证明单链表为无环单链表。

带环单链表的相遇点

复用上面的思路,既然单链表带环,当快指针pFast与慢指针pSlow相等时,即相遇时刻,此时返回任意一个指针就是相遇点,写出相遇点的代码可以方便后面入口点的调用。

环的入口点/环的长度

画一张剖析图方便理解,可以很清楚的看出各分段之间的关系,下面我会用数学方法来推导最终的公式。

上面的证明过程已经分析的足够清楚了,也就是说相遇点到入口点的n倍距离就是链表头部到入口点的距离,第一次相遇的点也必然是入口点。既然已经找到了相遇点,那么环的长度也就显得很简单了,通过从相遇点循环到相遇点,走过的节点即是环的长度。

链表的面试题还是很多了,我尽量把每一个链表的面试题都剖析一下,像上面这样的环的入口点,我也曾经写错过,只希望几个月后的面试不会重蹈覆辙。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:有环单链表的入口点/相遇点/环的长度 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情