Java でリンク リスト構造があるとします。これはノードで構成されています。
class Node {
Node next;
// some user data
}
そして、最後のノードを除く各ノードは次のノードを指し、最後のノードの次のノードは null です。リストにループが含まれる可能性があるとします。つまり、最後のノードは null ではなく、リスト内のその前のノードの 1 つへの参照を持ちます。
最も良い書き方は何ですか
boolean hasLoop(Node first)
true指定されたノードがループを含むリストの最初のノードである場合は を返し、そうでない場合はを返すのでしょうかfalse? 一定量のスペースと妥当な時間がかかるように記述するにはどうすればよいでしょうか?
ループを含むリストは次のようになります。
ベストアンサー1
活用できるフロイドのサイクル探索アルゴリズムウサギとカメのアルゴリズムとしても知られています。
アイデアは、リストへの参照を 2 つ用意し、それらを異なる速度1で移動することです。1 つはノード単位で前方に移動し、もう1 つはノード単位で前方に移動します2。
- リンクリストにループがある場合、それらは必ず出会います。
- それ以外の場合、2 つの参照のいずれか (またはそれらの
next) が になりますnull。
アルゴリズムを実装する Java 関数:
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}