题解 | #链表中环的入口结点#
链表中环的入口结点
http://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4
证明 起点到入口结点距离 = 快慢指针第一次相遇点到结点距离 + k* 环长
A--B==C
起点 A,入口节点 B,第一次相遇点 C
距离 AB 记为 a,距离 BC 记为 b,距离 CB 记为 c
则,第一次相遇慢指针走了 a + b,快指针走了 a + b + k * 环长,即 a + b + k ( b + c ),其中 k = 1, 2, 3, ..
由快慢指针的关系,有 2 * (a + b) = a + b + k * ( b + c )
化简得:a = (k - 1) * ( b + c ) + c
证明:慢指针slow与快指针fast相遇的时候,慢指针未走过整个环
A--B==C
起始节点A,入口节点B,第一次相遇节点C,环长记为L
slow的速度为1,fast的速度为2
- 设:当slow到达入口节点B的时候,fast所在位置为D,显然此时D在环上。
此时可认为fast落后于slow从D到入口节点B那么远,显然DB小于环长L。 - 第一次相遇的时刻也就是fast从D开始追上处于B位置的slow的时刻。
根据slow与fast的速度,容易算得从slow处于位置B到第一次相遇时slow走过的路程为DB,fast走过的路程为2DB。 - 显然DB小于环长L,所以第一次相遇的时候slow未走过整个环。
证明:slow1从起始节点A与slow2从相遇节点C同时以相同的速度出发,slow1到达B的时候与slow2相遇
- 当第一次相遇的时候,fast走过的路程AB + BC + k(BC + CB) 等于 slow走过的路程为AB+BC 的两倍,其中k=1,2,3...
- 所以得到等式:2(AB + BC) = AB + BC + k(BC + CB)
- 化简得到 AB = k(BC + CB) - BC
- 再化简得 AB = (k - 1)(BC + CB) + CB
- 上面等式的含义就是节点A到节点B的路程等于k - 1 个环长L 加上 相遇节点C 到 入口节点B 的距离
- 即slow2从C走到B,再转k - 1圈,走过的距离与AB相等,而此时slow2也在入口节点B处。