本帖最后由 grassgigi 于 2014-6-26 10:01 编辑 |
K -- number of nodes before cycle start point in list
C -- number of nodes of cycle
Let the faster nodes forward 2 steps each turn, slow nodes forward 1 step each turn.
S -- how many steps slow node passed when two nodes meet.
X -- the node distance between the meet point and cycle start point
When two meet each other, lets say first nodes go through whole cycle M times, second nodes go through whole cycle N times, we have:
equation 1 => S = K + M *C + X
eq 2 => 2S = K + N * C + X
eq 2 - eq 1 => S = (N - M) * C
Replace S in eq 1 => X = (N - M)C - K - M = (N - 2M)C - K
So at their meeting point, after K more steps the slower node will arrive the cycle start.
Inorder to do that we just need to put the fast node back to head and go one step forward each time, as well as slow node, until they meet each other again in the cycle start point