剑指Offer(五十五):链表中环的入口结点

2018年1月24日11:46:25 4 6,743 °C
摘要

一个链表中包含环,请找出该链表的环的入口结点。

剑指Offer(五十五):链表中环的入口结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

一个链表中包含环,请找出该链表的环的入口结点。

1、思路

可以用两个指针来解决这个问题。先定义两个指针P1和P2指向链表的头结点。如果链表中的环有n个结点,指针P1先在链表上向前移动n步,然后两个指针以相同的速度向前移动。当第二个指针指向的入口结点时,第一个指针已经围绕着揍了一圈又回到了入口结点。

以下图为例,指针P1和P2在初始化时都指向链表的头结点。由于环中有4个结点,指针P1先在链表上向前移动4步。接下来两个指针以相同的速度在链表上向前移动,直到它们相遇。它们相遇的结点正好是环的入口结点。

剑指Offer(五十五):链表中环的入口结点

现在,关键问题在于怎么知道环中有几个结点呢?

可以使用快慢指针,一个每次走一步,一个每次走两步。如果两个指针相遇,表明链表中存在环,并且两个指针相遇的结点一定在环中。

随后,我们就从相遇的这个环中结点出发,一边继续向前移动一边计数,当再次回到这个结点时,就可以得到环中结点数目了。

2、代码

C++:

Python:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  2   博主  2

    • avatar MISS Yure 来自天朝的朋友 Safari浏览器 Mac OS X 10_12_6 上海市 上海理工大学 4

      666

      • avatar Daryl Liu 来自天朝的朋友 谷歌浏览器 Windows 10 陕西省宝鸡市 电信 0

        思路很清晰,学习了👍

          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

            @Daryl Liu 感谢支持啦~