c - 1回のトラバーサルでのリンクリストの中点？

Question

ループが始まる単一リンクリストのポイントを見つけようとしています。私が考えたのは、2つのポインターを*遅く、*速く、一方が他方の2倍の速度で動くことでした。リストにループがある場合は、ある時点で

    5-6-7-8
    |     |
1-2-3-4-7-7

遅い=速い

リストが一度だけトラバースされるようにする別のエレガントな解決策はありますか？

Answer 1

Your idea of using two walkers, one at twice the speed of the other would work, however the more fundamental question this raises is are you picking an appropriate data structure? You should ask yourself if you really need to find the midpoint, and if so, what other structures might be better suited to achieve this in O(1) (constant) time? An array would certainly provide you with much better performance for the midpoint of a collection, but has other operations which are slower. Without knowing the rest of the context I can't make any other suggestion, but I would suggest reviewing your requirements.

Answer 2

I'm assuming that this singly linked list is ending with NULL. In this case, slow pointer and fast pointer will work. Because fast pointer is double at speed of slow one, if fast pointer reaches end of list slow pointer should be at middle of it.

Answer 3

これはある種のインタビューの質問だったと思います。

リストにループがある場合、1 回のトラバーサルでそれを行うには、ファスト ウォーカーがリストを通過するときにノードを訪問済みとしてマークする必要があります。速い歩行者が NULL または既にアクセスしたノードに遭遇すると、反復が終了し、遅い歩行者は中間点になります。

ノードを訪問済みとしてマークする方法は多数ありますが、外部マップまたはセットを使用できます。ノード自体でノードを直接マークすると、マークをクリーンアップするために別のトラバーサルが必要になります。

編集：したがって、これは中間点を見つけることではなく、すでにアクセスしたノードを再訪せずにループを検出することです。マーキングはそのためにも機能します。リストを走査してノードをマークするだけです。NULL をヒットした場合、ループはありません。訪問したノードにヒットすると、ループが発生します。マークにカウンターも含まれている場合は、ループの開始点もわかります。