リンク リストの中間要素を取得する Python プログラム (1 回の反復で完了)

リンク リストは、データを個別のメモリ位置に保存するために使用されます。データ項目を含むノードはポインタを使用してリンクされます。各ノードは 2 つのフィールドで構成されます。最初のフィールドはデータの保存に使用され、2 番目のフィールドには次のノードへのリンクが含まれます。

ブルートフォースクラッキングテクノロジー

リンク リストの中間要素を見つけるための総当たり手法は、NULL が見つかるまでリンク リスト全体を反復してリンク リストの長さを見つけ、その長さを 2 で割って中間要素を取得します。リンクされたリストのインデックス。中間要素のインデックスを取得した後、リンク リストを最初から再度繰り返し、必要なインデックスに達したときに停止します。このインデックスのデータ項目は中間要素を示します。

• 「temp」という名前の変数を HEAD をポイントし、「len」を 0

に初期化します。

• temp を使用して、NULL に達するまでリンク リストを反復処理し、各ノードで "len" を 1 ずつ増分します。

• リンクリストの長さを取得した後、tempを再度HEADに初期化します。リンクされたリストを len//2 まで繰り返します。

低速ポインタと高速ポインタの使用 (単一反復)

2 つのポインターを使用して、リンクされたリストを移動します。 1 つは「スロー ポインター」と呼ばれ、もう 1 つは「ファスト ポインター」と呼ばれます。

高速ポインタは、低速ポインタの 2 倍の速度で移動します。

高速ポインタがリンク リストの最後に到達すると、低速ポインタは中間ノードに配置されます。

したがって、中間ノードの内容を直接出力できます。

＃＃＃例＃＃＃

次のリンクのリストを検討してください。真ん中の要素は 3 です。

高速ポインタはリンク リストの最後のノードに到達し、低速ポインタはノード 3 を指しています。したがって、3 は指定されたリンク リストの中央の要素です。ここで、6 つのノードについて考えてみましょう。

＃＃＃例＃＃＃

高速ポインタが NULL に達し、低速ポインタが 4 番目のノードを指しています。したがって、真ん中の要素は 4 になります。 ＃＃＃アルゴリズム＃＃＃

「slow」と「fast」がリンクされたリストの HEAD を指すようにします。

高速ポインタと
• fast.next

  が NULL

に等しくなるまで、高速ポインタを 2 ずつ、低速ポインタを 1 ずつ増やします。

• スロー ポインターの値を出力します。

時間計算量は O(n) です。

• リーリー ＃＃＃出力＃＃＃ ああああ

以上がリンク リストの中間要素を取得する Python プログラム (1 回の反復で完了)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。