特定の単一リンクリストがループであるかどうかを特定する方法はありますか？

Question

インタビューで、単一のリンクされたリストにループがあるかどうかを尋ねられました。私はこのSOを検索し、いくつかの答えを見つけましたインタビュー質問：どのようにリンクリストのループを検出するには？と私は前にそれらの答えを知っていたが、何とか私は友人との長い時間の後の私の討論から私が心に持っていた異なった答えをしたが、答えが正しいかどうか分からなかった。自分で試してみると、期待どおりに動作します。何とか面接官が幸せではない。誰かがこれで間違っていることを明確にすることはできますか？

struct node { 
int flag; 
struct node *next; 
} 

ここでの私の考えは二つのポインタを使用してvariantlyホップが、単一のポインタを使用し、トラバースしない各ノード例：私だけはどうしたらこれが1ときにフラグ変数を設定されている

node = node->next; 

を今まで私がノードを通過し、効率よりも

if (node->flag) 
{ 
    return TRUE; // implies list is a loop 
} 
else{ 
    node->flag = 1; 
} 

その他の各時間などを確認し、このアプローチでは何が間違っているのですか？

Answer 1

余分な整数変数flagを使用していて、マシン内のsizeof(int)が4バイトで、リンクされたリストに100,000のノードがあるとすると、400,000バイト以上使用することになります。約390M/.38G

O（n）であっても、リンクリストのすべてのノードについてflagをリセットするには、100,000ノードをすべてトラバースする必要があります。そのオーバーヘッド。

flagベースのソリューションと2変数ソリューションを比較すると、ほぼ同じ計算時間ですが、2変数ソリューションは、ループを識別するために390Mのメモリを使用しないため、非常にメモリ効率が良いと考えられます！

Answer 2

あなたのアプローチはさらに効率的ですが、リスト表現を変更できるという事実に依存しています。同じ質問をしたところ、私は同じ解決策を出しましたが、面接官は私に、私はどのような方法でもリストを変更することはできないと言いました。

Answer 3

各リスト項目を保存するには追加データ（flag）が必要です。したがって、あなたのアプローチはO（N）の追加メモリーを必要とし、2つのポインターを使用するアプローチはO（1）メモリーしか必要としません。

あなたはアプローチがメモリ効率的ではありません。

Answer 4

2つのポインタを使用するのではなく、答えが間違っているわけではなく、ただ1つのポインタを使用します。しかし、インタビューのためのこの答えを与えることは、あなたが一つの基本的な前提を見過ごす上で質問します。

あなたは、絶対にそうする必要があるまで、与えられた問題のデータ構造を変更することは、一般的には想定されていません。この観点から考えてみましょう。

リンクリストではなく、会社が開発したアプリケーションで、特定のものがそのアプリケーションに当てはまるかどうかを調べる必要がある場合はどうすればいいですか？この場合、アプリケーションコードを変更することは避けられません（やむを得ない限り実用的ではありません）が、あなたが持っているものを回避することが望ましいでしょう。

このため、あなたのインタビュアーは答えに満足していませんでした。あなたはいつも他の答えに加えて、この答えを与えることができますが、あなたの答えの答えとして与えることはできません。

Answer 5

おそらくHare and Turtleとなります。 Turtleは一度に1つのアイテム、通常はHareが2回、2つのアイテムずつ表示されます。 HareがTurtleに合格すると、ループが発生します。

編集：：私はこの提案が既にhereであることを知り、彼のコメントで既にOPによって拒否されていることがわかります。