c - Cでリンクリストをランダムにシャッフルする方法

Question

リンクリストがあり、関数を実装したい：

Random_Shuffle_List (struct node **Headptr)-すべてのノードが元の位置からランダムに移動するようにリストを出力します。

これを達成するための効率的なアルゴリズムを手伝ってください。

Answer 1

単純なアプローチをお勧めします。

1. 各ノードを指すポインター配列を作成します。
2. 配列をシャッフルします。これは、リンクされた構造をランダム化するよりもはるかに簡単です。
3. 配列の順序でノードをステップ実行して、リストを「再スレッド化」します。

もちろん、これは比較的少量の余分なメモリを使用しますが、リンクされたリストで直接作業するアプローチよりも、実装（および理解）時間とおそらく実行時間の点で「効率的」だと思います。

Answer 2

リンクされたリストを逆にして、中間ノードと終了ノードを交換するだけです。これでうまくいくと思います。複雑さはO(n)になります。

Answer 3

1. リンクされたリスト内のノードの数を数えます。n
2. との間の2 つのランダムな整数 ( a、b)を生成します。0n
3. a2 つのノードと を入れ替えbます。
4. 上記を数m回繰り返します。

これは良い方法ではありませんが、@unwind の提案のように追加のメモリは必要ありません。

@unwind のソリューションでできることの 1 つは、ウィンドウを使用することです。

1. 言うウィンドウの長さを修正w
2. 3. 長さw(ウィンドウ) の重複しない 2 つのサブリストを形成できるように、リンク リスト内の 2 つのランダム ノードを選択します。
3. リスト内の各ノートを指す 1 つのウィンドウにそれぞれ 2 つの配列を作成します。
4. 各ウィンドウをシャッフルする
5. 2 つのウィンドウ間でポインタをシャッフルする
6. ノードを再リンクする
7. 上記のウィンドウの選択、シャッフル、および再リンクのm時間を行います。