首页 > 其他 > 详细

环状链表的相遇节点为出发节点。

时间:2018-07-16 00:24:14      阅读:221      评论:0      收藏:0      [点我收藏+]

题目:

一个环状链表(收尾相连),两个指针 head1 和 head2 从同一个节点出发,head1 每次 走一步,head2 每次走两步,请证明,两个指针第一次相遇于出发的节点 

思路:假设两个节点相遇时,慢节点距离出发节点为c,环状链表中有n个节点。

慢节点速度v,经过t时间相遇后的路程为:c = v*t;

快节点速度2*v,经过t时间相遇后的路程为:n+c = 2*v*t;

由上述两步得到:n+c = 2*c, n=c,所以经过n个节点即出发节点即为相遇节点。

环状链表的相遇节点为出发节点。

原文:https://www.cnblogs.com/yingpu/p/9315629.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!