题解 | #链表中环的入口结点#

链表中环的入口结点

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

  1. 设:当slow到达入口节点B的时候,fast所在位置为D,显然此时D在环上。
    此时可认为fast落后于slow从D到入口节点B那么远,显然DB小于环长L。
  2. 第一次相遇的时刻也就是fast从D开始追上处于B位置的slow的时刻。
    根据slow与fast的速度,容易算得从slow处于位置B到第一次相遇时slow走过的路程为DB,fast走过的路程为2DB。
  3. 显然DB小于环长L,所以第一次相遇的时候slow未走过整个环。

证明:slow1从起始节点A与slow2从相遇节点C同时以相同的速度出发,slow1到达B的时候与slow2相遇

  1. 当第一次相遇的时候,fast走过的路程AB + BC + k(BC + CB) 等于 slow走过的路程为AB+BC 的两倍,其中k=1,2,3...
  2. 所以得到等式:2(AB + BC) = AB + BC + k(BC + CB)
  3. 化简得到 AB = k(BC + CB) - BC
  4. 再化简得 AB = (k - 1)(BC + CB) + CB
  5. 上面等式的含义就是节点A到节点B的路程等于k - 1 个环长L 加上 相遇节点C 到 入口节点B 的距离
  6. 即slow2从C走到B,再转k - 1圈,走过的距离与AB相等,而此时slow2也在入口节点B处。
全部评论

相关推荐

点赞 收藏 评论
分享
正在热议
# 牛客帮帮团来啦!有问必答 #
1153822次浏览 17172人参与
# 通信和硬件还有转码的必要吗 #
11273次浏览 101人参与
# OPPO开奖 #
19433次浏览 269人参与
# 和牛牛一起刷题打卡 #
19198次浏览 1641人参与
# 实习与准备秋招该如何平衡 #
203610次浏览 3629人参与
# 大厂无回复,继续等待还是奔赴小厂 #
5089次浏览 33人参与
# 不去互联网可以去金融科技 #
21071次浏览 259人参与
# 通信硬件薪资爆料 #
266158次浏览 2484人参与
# 国企是理工四大天坑的最好选择吗 #
2242次浏览 34人参与
# 互联网公司评价 #
97799次浏览 1280人参与
# 简历无回复,你会继续海投还是优化再投? #
25053次浏览 354人参与
# 0offer是寒冬太冷还是我太菜 #
455121次浏览 5130人参与
# 国企和大厂硬件兄弟怎么选? #
53944次浏览 1013人参与
# 参加过提前批的机械人,你们还参加秋招么 #
14650次浏览 349人参与
# 硬件人的简历怎么写 #
82306次浏览 852人参与
# 面试被问第一学历差时该怎么回答 #
19436次浏览 213人参与
# 你见过最离谱的招聘要求是什么? #
28805次浏览 249人参与
# 学历对求职的影响 #
161310次浏览 1805人参与
# 你收到了团子的OC了吗 #
538983次浏览 6390人参与
# 你已经投递多少份简历了 #
344418次浏览 4964人参与
# 实习生应该准时下班吗 #
97094次浏览 723人参与
# 听劝,我这个简历该怎么改? #
63535次浏览 622人参与
牛客网
牛客企业服务