1

whileループを使用して単一のリンクリストのノードを反復処理する方法は知っていますが、値が一致する場合に特定のノードを削除するにはどうすればよいですかint value?頭がこれに巻き付いた。

class Node
{
public int value ;
public Node next ;
}

これは、ノードを反復する while ループであり、最初の望ましくない値を見つけた後に停止します。このリンクされたリストには、値が望ましくないノードが複数ある可能性があるため、望ましくない値を持つノードの削除を実装するためにどの追加コードを作成する必要があるかについて混乱しています。

while ((currentNode != null) && (currentNode.Value != UndesiredValue))
   currentNode = currentNode.next;

出力例:

連結リストに整数がある場合

5、7、8、9 3、5、5、2

望ましくない値が 5 の場合、5 のノードが削除されるため、リストは 7、8、9、3、2 になります。

4

2 に答える 2

3

ヒント: これは削除前のリスト (の一部) です。

+----------------+
| previous Node  |
+----------------+
| some value     |        +----------------+
|     Next ------------>  | currentNode    |
+----------------+        +----------------+
                          | UndesiredValue |       +-----------+
                          |    Next  ------------> | next Node |
                          +----------------+       +-----------+

これは、削除後のリスト (の一部) です。

+----------------+
| previous Node  |
+----------------+
| some value     |                                 +----------------+
|     Next ------------------------------------->  | next Node      |
+----------------+                                 +----------------+

ご覧のとおり、前Nextのノードの参照を変更するだけで十分です。

(これは明らかに宿題またはトレーニングの問題であるため、C# でリンクされたリストを再実装する別の理由はわかりません。正しい軌道に乗るにはこれで十分です。)

ヒント 2:

  • リストを反復処理するときは、前のノードと現在のノードへの参照を保持します (これは、ループ本体内の 1 つの単純な C# 割り当てです)。
  • 何かを見つけたら、前Nextのノードの参照を更新します (これも単純な C# 割り当ての 1 つです)。
  • 最初の要素を削除するには特別な注意が必要ですが、アルゴリズムの残りの部分が機能した後でそれを処理しましょう。
于 2013-10-16T07:36:38.640 に答える
0

終了する可能性のある状況を確認する必要があります。削除には2つの主要なシナリオがあります

  • 最初の要素を削除します
  • 他の要素を削除します

実装では両方を処理する必要があります。最初のものを処理するのは簡単です。指定された値で主要な要素を渡すだけです

var currentNode = head; //head points to the first element of type `Node`
while(currentNode != null && currentNode.Value == undesiredValue) {
     currentNode = currentNode.Next; 
}
head = currentNode;

その後、望ましくない値を持つ要素を見つけてリストから除外する必要があります

//at this point the head should not be removed
while(currentNode != null && currentNode.Next != null){
   //skip all elements with the undesired value
   var next = currentNode.Next;
   while(next != null && next.Value == undesiredValue){
       next = next.Next;
   }
   currentNode.Next = next;
}

内側のループは、前の単純なループとまったく同じように動作するため、コードをいくらか要約することもできますが、このコードは、設計上の問題に取り組むときに取るべきアプローチを示しています。各シナリオを解決する可能性のあるさまざまなシナリオを分析すると、同時にいくつかのシナリオを解決できる場合があります (たとえば、最後の要素を削除する 3 番目のシナリオがありますが、上記の 2 番目のシナリオと一緒に解決されます)。

于 2013-10-16T07:59:29.907 に答える