yuuka_maniaの日記: LeetCode #10 Linked List Cycle II
約二か月ぶりに再開。やるとまぁまぁ楽しいか。ただ、解法としては、slow pointer と fast pointer を使う解法が正攻法らしいので、それが自然とできるようにならないといけないかもしれない。
しかし、改めて、これは思いつかんわ...
1 -> 2 -> 3 -> 4 -> 5
^ |
+---------+
1 -> 2
1 -> 2 -> 3
1 -> 2 -> 3
1 -> 2 -> 3 -> 4 -> 5
hit
1 -> 2 -> 3 -> 4
1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 4
スタートから、ループの始まりまでを a
ループの始まりから、実際に交差するまでを b
slow の移動距離は、a + b
fast の移動距離は、a + b + X
ただし、fast は、あきらかに、二倍動いている。slow が、1 なら、fast は、2
slow が 2 なら、fast は、4、 slow が、3 なら、 fast は、6 なので。
つまり、 a + b の二倍で、2 * (a + b) 動いている。
fast の b が二倍なのはあきらか。
となると残りの 2a が示してるのは、a(最初の移動) + (hit 箇所からhit 箇所までの距離)
なので、hit 箇所からhit 箇所までの距離 は、a と同じということになる。
なので、もう一度最初から辿るのと、slow をそのまま動かしていって、ぶつかったら、それが
a の距離なので、期待する node となる。
LeetCode #10 Linked List Cycle II More ログイン