661 測定値

毎日のコーディングの問題: 1 回のパスでリンクされたリストから k 番目のインデックスを削除する

に Nicola Moro8m2023/06/26

長すぎる; 読むには

リンクされたリストと、リストから削除するインデックス要素「k」が与えられます。その後、リンクされたリストの先頭を返す必要があります。これらすべてをオンパスで実行する必要があります。つまり、リストを複数回ループすることはできません。方法を見てみましょう!

featured image - 毎日のコーディングの問題: 1 回のパスでリンクされたリストから k 番目のインデックスを削除する

リンクされたリストから k 番目のインデックスを 1 回のパスで削除する

おかえりなさい。別の問題を解決する必要があります。今日は、リンクされたリストとその要素の削除を扱います。リンクリストとは何かについて少し説明し、リンクリストを作成して、そこから要素を削除する方法を見ていきます。

始める前に、通常の免責事項を述べておきます。

これらの問題は、購読できる素晴らしいニュースレター「Dailycoding 問題」によって提供されます。ここ。ぜひチェックして、あなたの課題も解決してみてください！

私は専門プログラマーではありません。自分のショットを共有するのが好きなただの人です。アルゴリズムに対してより優れた、またはより高速なソリューションがある場合は、コメント欄に送信してください。これについてもう少し詳しく知りたいです!

面倒なことはもう十分です。問題に移りましょう！

この問題は最初に Amazon によって尋ねられました

リンクリストと整数kを指定すると、リストの末尾から k 番目のノードを削除し、リストの先頭を返します。
kはリストの長さより小さいことが保証されます。
これを 1 回のパスで実行します。

それでは、ここで何が起こっているのかを少し説明しましょう。リンクされたリストと、リストから削除するインデックス要素kが与えられています。その後、リンクされたリストの先頭を返す必要があります。

最後に、これらすべてを 1 回のパスで実行する必要があります。つまり、リストを複数回ループすることはできません。

また、インデックスkがリストに含まれていることも保証されているため、インデックス k がリストの実際の長さを超えているかどうかをチェックする必要はありません。

Go の構文はこの種の作業に最適であり、同時に非常に理解しやすいため、今日は Go を使用してアルゴリズムを構築します。

最初から始めましょう。単純なリンクされたリストを作成します。

リンクされたリスト

リンクリストの背後にある概念は非常に単純です。リンクリストはオブジェクト (通常はノードと呼ばれます) で構成されるリストであり、各ノードには値(ノードに実際に含まれる何か) と次のノードへのリンクという少なくとも 2 つのプロパティが必要です。

通常、ポインタは、あるノードから別のノードにジャンプするためのリンクとして使用されます。

また、リストの最初のノードは通常リストの先頭と呼ばれ、問題によって返されるように求められるノードでもあります。

以下にグラフィカルな例を示します。

左側の最初のノードはリストの先頭であり、その値 v0 とリストを次のノードn1にリダイレクトするメモリポインタP(n1)が含まれています。次のノードn₁には、その値と次のノードへのポインタP(n₂)などが含まれます。

もちろん、最後のノードには指すものが何もないため、そのポインターの値はnullになります。

作成するコードを見てみましょう。

コードは非常に単純です。内部ノード用とリンクリスト用の 2 つの構造を作成します。

先ほど見たように、ノードには 2 つのプロパティがあります。つまり、プロパティValueと、次のノードへのポインタとして*Nodeタイプを保持するプロパティNextです。

リンクリスト。リンクリストを「初期化」するための構造。リストのHeadというプロパティが 1 つだけあります。

その後、メイン関数でリストを初期化し、その頭にランダム値 10 のノードを与えます。

リンクリストを理解するための重要な点は、 HeadノードはタイプNodeであるため、本質的にNextプロパティを持ち、これに次のノードが含まれるというHeadです。この最後のノードには、次のノードにジャンプするためのNextプロパティが設定されます。

いくつかのノードをリストに追加すると、すべてがより明確になるので、実際にやってみましょう。選択肢は 2 つあります。非常に面倒な作業である手動で行うか、リンクリストクラスのメソッドを作成してノードを追加するかのどちらかです。それをチェックしよう！

ノードの追加: 変装した可変リスト

プログラミング経験がほとんどない場合でも、ほぼすべてのプログラミング言語で、最初に聞いたことがある概念の 1 つは、可変リストと不変リストの違いです。

名前が示すように、変更可能なリストは、操作して要素を追加できるリストです。代わりに、不変のサイズは固定されており、新しい要素を追加することはできません。しかし、なぜそうなるのでしょうか？

不変リストはメモリ内で連続しています。つまり、その要素はメモリに順番に格納されます。3 つの要素のリストの場合、最初の要素が 0x00 に格納されている場合、2 番目の要素は 0x01 に、最後の要素は 0x02 に格納されます。

CPU がメモリインデックスを 1 つずつ呼び出すだけなので、Python で固定配列、不変リスト、またはタプルを反復処理するのが非常に速いのはこのためです。

一方、可変リストは最初に初期化されたときのみメモリ内で連続します。その時点で、要素が追加されると、それらはもはや連続的ではなくなります。では、どうすればそれらをループできるでしょうか?

最初の開始の最後の要素には、その要素の後に追加されたポインタがあり、それによって to 要素が追加されるなどです。はい、可変リストは実際には、偽装されたリンクリストであることがよくあります。

それでは、コードを見てみましょう。

リンクリストのメソッドにメソッドAddNode追加しました。ノードを追加するプロセスは次のようになります。

まず、 Head値をcurrentという変数に保存します。

次に、次のノードが null になるまで、毎回次のノードでcurrent変数を更新するリンクリストをループします。現在いるノードに null ポインターがあると、リストの最後のノードにいることがわかります。

最後に、この最後のノードを新しいノードと新しい値で更新します (この新しいノードのNextポインターを空白のままにすると、null に設定されます)。

このプロセスを図的に表すと次のようになります。

main 関数でこのメソッドが正しく機能していることを確認し、リンクリスト内のノードの値を出力します。

ノードの削除

ここで最後の部分と問題の解決策を説明します。正しいインデックスを持つノードを削除します。まず、リンクリストからノードを削除するとはどういう意味でしょうか?考えてみると、リンクリスト内のノードは、前のノードに接続されている場合にのみ存在します。

たとえば、n-1ᵗʰ のNext値に null を与えると、nᵗʰ 値をリストから切り離すことができます。

削除したい要素が最後の要素ではない場合はどうすればよいでしょうか?そうですね、前の要素を次の要素に接続することで、要素のリンクを解除できます。

したがって、kᵗʰ 要素を削除するには、k-1ᵗʰ 要素を見つけて、それを k+1ᵗʰ ノードにリンクする必要があります。前のノード (k-1ᵗʰ)を保存する必要があります。

明らかに、リストに直接インデックスを付けることはできません。linkedlist linkedlist[n]のようなものを試してみると、エラーが発生するだけです。ただし、これを考慮すると、リストの先頭をインデックス 0、次のノードをインデックス 1 などとみなすことができ、以前と同様にノードをループすることもできます。

そこで私たちができることは、現在いるノードを追跡するカウンターを実装することです。

それではコーディングしましょう。

index属性を受け入れるRemoveNode関数を見てみましょう。その後、3 つの変数を初期化します。

previousNode 、前のノードを保持します

current 、ループ中に現在いるノードを保持します。

counter 、最初は 0 に等しく、リスト上の位置を保持します。

ここでは最初の if ブロックをスキップし、代わりに for ループに集中しましょう。 counter変数がindexより厳密に小さくなるまでループを開始します。各ループはその後、前のノードを現在のノードで更新し、現在のノードとカウンタの更新に進みます。

ループが中断すると、目的のインデックスの直前のノードにいることを意味します。必要なのは、前のノードのポインタprev.Next 、リスト内のこのノードの次のノードで更新することだけです。 current.Nextになります。次へ。最後に、リンクされたリストの先頭を返します。

ここで、削除するインデックスが 0 のインデックスを持つヘッドである場合はどうなるでしょうか?ループはcounter = 0およびindex = 0で開始されるため決して開始されず、条件は即座に false になります。この最初のケースは、先頭の if ブロックで管理できます。

基本的に、インデックスが 0 の場合、リンクされたリストの先頭をその隣のノードで直接更新して返すことができます。特に 31 行目に注目してください。 Go は、他の多くの言語と同様に、 value によって属性を関数に渡します。これは、関数が、渡している実際のオブジェクトではなく、渡されたオブジェクトのコピーを保持することを意味します。。

この概念は、次の例で明確に示されています。

 package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.

属性として渡された値のメモリアドレスを出力する関数を作成します。次に、main 関数で変数 a を作成し、そのメモリアドレスを出力します。次に、同じ変数を関数に渡し、そのメモリアドレスを出力します。

ご覧のとおり、試してみると結果は異なります。これは、属性が値として関数に渡されるためです。つまり、関数に渡すためだけにaのコピーが作成されることになります。

リンクリストに戻って、上記と同じ問題の実際の先頭を取得するには、ポインターを使用する必要があります。したがって、「実際の」 ll.Nodeに到達するには、そのポインタ*ll.Nodeを呼び出し、 *ll.Node = *ll.Node.Nextを使用してさらに移動する必要があります。

main 関数では、メソッドの呼び出し (たとえば、 ll.RemoveNode(0)およびll.RemoveNode(2)の呼び出し) を追加し、ノード 0 とノード 2 が欠落している結果を確認できます。