解析思路
leetcode 中等难度,题目描述点击这里。
看到题目描述首先蹦出来的解法就是遍历链表,记录走过的节点,当某个节点第二次走到的时候说明该节点就是环的起点,当节点没有下个节点说明没有环。本方法很简单不做详细说明,用一个HashSet记录访问过的节点即可。
有没有更好的版本呢?当然是有的。通常使用快慢指针的办法来解决这类链表环的问题。思路如下:
- 定义两个指针slow(慢指针,每次走1个),fast(快指针,每次走两个),都从head出发。
- 每进行一次移动fast和slow间隔的节点就会+1,由此可以推断当slow进入环后,一定会和fast相遇
假设链表非环的长度为a,环的长度为b,fast走过的距离为f,slow走过的距离为s,当fast在环中循环n次后,fast,slow首次相遇,可得到如下表达式:
f=2s(f的速度是s的两倍)
f=s+nb(一定比s走的距离多n圈才会相遇)
由上面两个得到:s=nb,由于s走的距离肯定包含了a,可以得到s在环中走的距离为nb-a,只需要继续走a的距离就能刚好走到环的起点。
- 所以再加一个指针c从head开始,每次移动一格,当c和slow相遇时说明到了环的起点
java如下:
1 | package com.fanxb.common; |
本体存在一些变体也是一样的解法,
比如找到开始节点后的第n个节点,可在找到头后再遍历n次
比如找到开始节点前的第n个节点,一样的找到头后,再遍历一遍环得到环长度,再计算出需要遍历的次数,得到距离开始节点前的第n个节点