141.リンクリストサイクルleetcodejava

141 Linked List Cycle Leetcode Java

トピック：

リンクリストが与えられたら、そのリストにサイクルがあるかどうかを判断します。

ファローアップ：
余分なスペースを使わずに解決できますか？

アイデア：

単一リンクリストにリングがあるかどうかを判断し、速度ポインタを使用してそれを解決します。リンクリストのリングは、円形の遊び場に相当します。円形の遊び場で2人が無限ループで走っていると仮定すると、速い方が遅い方に追いつくことができます。同様に、リンクリストにリングがあるかどうかを判断する場合は、高速ポインタと低速ポインタを設計できます。高速ポインタと低速ポインタがリングに入るときに、2つのポインタが最終的に出会う場合は、リンクリストにリングがあることを示す必要があります。次に、高速ポインタと低速ポインタのステップ長を考慮する必要があります。遊び場を運営するという観点からは、どんなに遅くても速くても、彼らは間違いなく出会うでしょう。同様に、リンクリストでは、速度ポインタのステップ長を自由に指定することもできます。これは、実行するラップ数にすぎません。に

したがって、高速ポインタと低速ポインタを設定します。ポインタが出会うと、ループがあることがわかります。高速ポインタがnullに移動し、遭遇がない場合、ループはありません。

プログラム：

public class Solution { public boolean hasCycle(ListNode head) { if(head==null||head.next==null||head.next.next==null) return false ListNode fast=head ListNode slow=head while(fast!=null&&fast.next!=null){ fast=fast.next.next slow=slow.next if(fast==slow) return true } return false } }注：リンクリストに少なくとも2つのノードがある場合にのみ、ループが発生する可能性があり、アルゴリズムはループの判断条件に注意して適切な判断を開始します。