再帰を使用してソートされたリンクリストから重複を削除します

#リンク リストは、一連の要素が結合されたものです。各リストにはヘッダーと一連のノードがあり、それぞれが現在のノードのデータを保持し、次のノードにリンクします。リンクリストの基本操作は、挿入、削除、検索、削除です。

並べ替えられたリンク リストから重複を削除する

ノードを削除する方法の 1 つは、再帰を使用することです。その考え方は、各ノードを隣接するノードと比較し、それらが等しい場合には重複したノードを削除することです。

再帰呼び出しは次のノードに戻ります。したがって、次の要素では、

current_node->next = our_function(node->next) のような再帰関数を呼び出します。

再帰を信頼し、current_node->next には重複要素のないリンク リストが含まれるようになりました。

メインの方法では、リストに最初から入札します -

リーリー ＃＃＃アルゴリズム＃＃＃

再帰を使用して並べ替えられたリンク リストから重複を削除するプロセスは次のとおりです。

ステップ 1
• - すべての値を順番に並べ替えたリンク リストを作成します

ステップ 2
• - リンクされたリストが存在しない場合、プログラムは終了します。

ステップ 3
• - リンク リストが存在する場合は、ヘッド ノードの次の値をヘッド ノードの値と比較します。両方の値が同じ場合は、ヘッダーを削除します。

ステップ 4
• -

  ステップ 3 は再帰的に実行され、リストがそれ自体から重複する値をすべて削除するまで、各ノードをヘッドとして扱います。 。 ステップ 5

  - 取得される出力は、異なる値を持つソートされたリンク リストです。

• ＃＃＃例＃＃＃ たとえば、次の値を持つソートされたリンク リストがあります -

1->1->1->2->3->3->4

再帰を使用して、上記の並べ替えられたリンク リストから重複を削除する C プログラムを見てみましょう -

リーリー

その後、現在のノードがリンク リストに含まれているかどうかを確認します。現在のノード -> 次のノードから取得した満足のいくリンク リストがそのノードと同じ値を持つ場合は、そのノードを含めません。そうでない場合は、そのノードを含めます。

Note

- 現在のノードが NULL の場合、再帰の基本条件を返します。

＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

再帰呼び出しで見たように、次の呼び出しで問題の残りの部分で期待される結果が達成されると信じています。現在の副問題を解決したところです。これを念頭に置いて、現在の要素を含めることができるかどうかを確認し、リンク リストの残りを再帰呼び出しに渡し、その時点から有効なリンク リストが得られることを信頼します。リンクされたリスト全体を走査すると、このメソッドの時間計算量は O(n) になります。

以上が再帰を使用してソートされたリンクリストから重複を削除しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。