0

あるインタビューで、リンク リスト内のループ ノードを検出し、ループ内のノードの数をカウントするように依頼されました。flyod アルゴリズムを知らなかったので、独自のアプローチを見つけようとしました。

このシナリオでは、2 つのノードのアドレスが同じノード (ループ ノード) を指します。

例えば。

1-->2-->4-->5-->7-->3-->4

ここで 2->next と 3->next は同じで、これは 4 のアドレスです。これは、リンクされたリストにループがあり、4 がループ ノードであることを意味します。また、4 から 4 にトラバースすると、ループ内のノードの数が得られます。

このアプローチを進める方法はありますか????

4

1 に答える 1

1

もちろん、すでにアクセスしたアドレスのセットを維持することで、サイクルを自明に見つけることができます。ループのサイズに関心があるので、代わりにこれをマップにすることができます: address->count. カウントは、対応するアドレスのノードを訪問したときに訪問したノードの数です。テーブル内にすでにノードがあることがわかった場合は、現在のテーブルからテーブル内のカウントを差し引くことで、ループ サイズを取得できます。もちろん、ノード自体で「訪問済み」ビットとカウントを維持することで、同じ効果を得ることができます。その場合、別のマップは必要ありません。

于 2016-05-15T01:24:03.347 に答える