[LC 142]. Linked List Cycle II

数学题。容易想到用slow和fast两个pointer。但如何让两个pointer在circle起点处meet?首先搞清一个问题:假设circle length是r,list起点到circle起点距离是s,list起点到第一次相遇距离是k,circle起点到第一次相遇点距离是m,即s+m=k。由于k是slow和fast相遇点,所以2k-k = nr,n是一个整数。所以k = nr, s + m = nr。也就是说 s steps 和 m steps 加起来就是一圈。那么k的位置,距离circle起点已经走了m步,所以如果两个pointer分别从list起点和k处出发的,每人一次只走一步的话,那么他们会相遇在circle起点处。

circle

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s