パスワードを忘れた? アカウント作成
15818804 journal
日記

yuuka_maniaの日記: LeetCode #10 Linked List Cycle II

日記 by yuuka_mania

約二か月ぶりに再開。やるとまぁまぁ楽しいか。ただ、解法としては、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 となる。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

にわかな奴ほど語りたがる -- あるハッカー

読み込み中...