0%

环形链表

题目描述

142. 环形链表 II - 力扣(LeetCode)
给定一个链表,返回链表入环的第一个节点。无环返回null。
linkList.jpg

解题思路

环形链表问题,通用的解法,是通过设置双指针,

1
2
let runSlow = head
let runFast = head

将 runFast 的速度,设置为2,runSlow 的速度设置为 1,当 runFast 所在节点等于 runSlow 所在节点代表追上了。

我们可以思考若有环 runFast 追上 runSlow 跑了几圈?如果头节点到环入口 R 的距离很远,而环很小,runFast 以双倍的速度很早就到环了,所以可能跑 N 圈,如果距离较近,而环很大,第一圈就会追上了。

然而无论如何 runSlow 跑的第一圈就会被追上
为何如此呢?第一种情况,头节点到环入口 R 的距离很远,runFast肯定早到了,并且可能跑了不止一圈了,已知,runSlow 跑一圈,runFast 可以跑两圈,如果是正常跑,runFast 在 runSlow 到达环入口 R 的第一圈便可追上,而runFast是穿越空间式的跳过两个节点跑,即使这样,runFast再多跑一圈即可追上。runFast 跑两圈以内,runSlow肯定就跑了一圈以内。

1
2
3
4
5
6
7
while(runFast && runFast.next){
runFast = runFast.next.next
runSlow = runSlow.next
if (runFast === runSlow){
break
}
}

如果有环,到这里我们已经能够得到,runFast 和 runSlow 的相遇点了。
linkListRYS.jpg

题解:
相遇时:

  • runSlow 走距离为:R + Y;
  • runFast 走的距离为:R + n(Y+S) + Y
  • R + n(Y+S) + Y = 2(R + Y)
  • (n-1)Y + nS = R

只要以上等式成立即可,可以任意取n,这里取n为1:R = S,
也就是入口点的距离等于相遇点到这一圈终点的距离。

这是我知道了 R=S 这个结论后,再推倒的,如果不知道结论,本弱还在设圈的周长的未知数呢。并且最后一步的思想很关键。任意取

所以根据这个结论,我们从起始点再放一个速度为1的节点,并且让runSlow继续跑,和这个新节点相遇的点就是入口点,这里为了节省那一点点内存,可以让runFast受累一下,让他从新从head开始以1的速度跑。

1
2
3
4
5
6
7
8
runFast = head
while(true){
if(runFast == runSlow){
return runFast
}
runFast = runFast.next
runSlow = runSlow.next
}

知识积累

  • R = S
  • 不相关的参数可以任意设