C#和.Net框架

进阶问题

为什么快慢指针一定会相遇

---

• 如图,假设非环长a,环长b,相遇时距离入环口c.
• 假设快指针每次移动2个单位,慢指针每次移动1个单位.
• 当慢指针走到环的入口时,移动了a的单位,此时快指针移动了2a个单位.
• 此时快指针在环中的位置是(2a-a)%b = a%b
• 此时快慢指针相距b - a%b的距离.
• 由于快指针每次比慢指针多移动1个单位,则还需b-a%b次移动两者相遇.

两者需要移动多少次才能相遇

• a + b - a%b

为什么慢指针入环第一圈没走完的时候就会和快指针相遇?/慢指针要走多少圈才能和快指针相遇

• 根据上述推导,在慢指针如环的时候,快指针在a%b处
• 只需再走b-a%b就能相遇(b-a%b < b)

为什么快指针移动2步,移动其他步数可以吗.

• 如果快指针每次移动x步，x>1.
• 当慢指针走到环的入口时,移动了a的单位,此时快指针移动了xa个单位.
• 此时快指针在环中的位置是(xa-a)%b = [(x-1)a]%b
• 此时快慢指针相距b - [(x-1)a]%b的距离.
• 那么最终则需要 a + (b - [(x-1)a]%b)/(x-1)步才能相遇,此时该值不一定是整数,所以移动其他步数不一定相遇.

为什么第一次不相遇，之后就不可能相遇.

• 假设慢指针在环入口的位置走了a+nb步.
• 则快指针xa+xnb步,其中xnb相当于绕环xn圈,相当于此时快指针一定在距离环xa处,重复上述的操作.

如何找到入环结点

• 根据上述推导后
• 当快指针和慢指针相遇的位置是: a + nb + (b - a%b)(nb为快指针绕环的圈数)
• 又因为慢指针在第一圈一定能和快指针相遇,所以快指针的位置还等于慢指针的2倍，即: 2(a+ b - a%b)
• 联立两者得: a = (n-1)*b + a%b
• 我们知道快慢指针相遇时的位置是b-a%b,我们加上a得:b - a%b + a = b-a%b +(n-1)*b + a%b = n*b
• 所以我们只要让相遇时的指针再走a个单位就能到入环结点.