链表中环的情况

参考文章:

  1. 判断单链表里面有没有环
  2. 《剑指offer》面试题56
  • 怎么判断是否有环?
    用两个指针,一个一次步进一步,一个一次步进两步,如果最终两个指针相遇,那么有环
    具体证明见参考文章1

  • 怎么判断环的大小?
    在上面相遇后,两个指针继续走直到再次相遇,慢指针走的步数就是环的大小

  • 怎么判断环的节点?
    经过以上两步得到环的大小,可以转化为求两个链表的公共节点的问题了。

问题转化为求两个相交链表的公共子节点,其中一个比较短的链表是从0开始,到环的起始点,另外一个比较长的链表是从0开始,经过环的起点,再到达环的起点,长的链表比短的链表多出环的长度L。求两个相交链表的公共节点我们都知道:设置一个前后指针,前指针先走L步,然后再快慢指针一起走,第一个相遇的节点就是。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • //leetcode中还有花样链表题,这里几个例子,冰山一角 求单链表中结点的个数----时间复杂度O(n)这是最...
    暗黑破坏球嘿哈阅读 1,558评论 0 6
  • 链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一...
    JohnnyShieh阅读 4,999评论 0 9
  • 参考链接 基本数据结构:链表(list) 线性表 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元...
    梦即是幻阅读 546评论 0 3
  • 链表是线性表的一种。线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系,...
    骑摩托马斯阅读 682评论 0 3
  • 转载请注明出处:http://www.jianshu.com/p/c65d9d753c31 在上一篇博客《数据结构...
    Alent阅读 3,544评论 4 74