循环链表指针追赶问题:A步长1,B步长3,何时相遇?
指针A每次移动一步,指针B每次移动三步,所以指针B相对于指针A的速度是每次移动两步,也可以说指针B每次追赶指针A两步。
假设从起始位置开始计算,指针A移动了x步,那么指针B移动了2x步。由于链表长度为100,所以x的取值范围为0到99。
当指针A移动x步后,指针A所在位置的编号为x % 100。同时,指针B移动了2x步,所在位置的编号为(3 * x) % 100。
为了使指针A和指针B再次指向同一节点,需要满足以下条件: x % 100 = (3 * x) % 100
化简得: 2x % 100 = 0
即2x是100的倍数。最小的满足条件的x是50,此时指针A移动了50步,指针B移动了100步。
所以,指针A和指针B需要同时移动100步才能再次指向同一节点。
原文地址: https://www.cveoy.top/t/topic/dV4Q 著作权归作者所有。请勿转载和采集!