环形链表

发表于 更新于

题目描述

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

解题思路

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

1
2
let runSlow = head
let runFast = head

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

因为 runFast 和 runSlow 同时出发，且 runFast 的速度为 runSlow 速度的两倍。
无论如何 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
}

知识积累

  • 入口点的距离等于相遇点到这一圈终点的距离
  • 不相关的参数可以任意设