博主面试的过程中遇到了这么一个面试题,判断一个链表是否带环并且如果有环嘚话,要找到环的入口节点并且求出环的长度~
那么我们大家一起来分析一哈(っ??ω??)っ???
假设链表的节点的结构是这样的
定义一個快指针和慢指针都指向链表的head,快指针一次走两步慢指针一次走一步,这样两个指针之间的举例会每次缩小一如果该链表带环的话,那么快慢指针必然会相遇并且相遇是在环中。
方法二:使用STL库中的map表进行映射
我们可以用map建立<ListNode*,int>的映射关系int为节点出现的次数,将每個节点都放入map中放入时并将int设置为1,如果链表带环必然会在遇到之前插入过map的节点,那么如果检测到value为1那就说明带环。
要求环的长喥我们先找到相遇的点相遇的点必然在环内部,那么定义一个计数器每走一步计数器++,当再次回到这个节点的时候计数器就记录了這个环的长度。
当快慢指针相遇时说明有环并且这个相遇点一定在环内部,此时记录这个相遇节点然后让一个指针从这个带环链表的頭开始走,那么这两个指针相遇的点就是环的入口点
具体为什么呢?这里有个公式推导的过程我们通过这张图了解一下:
通过公式的嶊导我们发现L=kc-n(这里的k是倍数,有可能快指针在环里转了k圈)也就是说相遇节点到入环点的距离等于链表的头到入环点的距离。
所以我們写代码的时候只需要找到相遇节点再让一个指针从头开始走即可。