参考文章:
- 判断单链表里面有没有环
- 《剑指offer》面试题56
怎么判断是否有环?
用两个指针,一个一次步进一步,一个一次步进两步,如果最终两个指针相遇,那么有环
具体证明见参考文章1怎么判断环的大小?
在上面相遇后,两个指针继续走直到再次相遇,慢指针走的步数就是环的大小怎么判断环的节点?
经过以上两步得到环的大小,可以转化为求两个链表的公共节点的问题了。
问题转化为求两个相交链表的公共子节点,其中一个比较短的链表是从0开始,到环的起始点,另外一个比较长的链表是从0开始,经过环的起点,再到达环的起点,长的链表比短的链表多出环的长度L。求两个相交链表的公共节点我们都知道:设置一个前后指针,前指针先走L步,然后再快慢指针一起走,第一个相遇的节点就是。