迭代链接列表以删除节点

Question

我知道如何使用with循环遍历单个链表的节点，但是如果某些节点的值与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，那么列表就变成7，8，9，3，2，因为有5的节点会被删除。

Answer 1

你应该看看你能在什么情况下结束。有两种主要的移除方案

• 删除第一个元素
• 删除任何其他元素

您的实现需要同时处理这两个问题。处理第一个问题是直接的。您只需用给定的值迭代传递前导元素。

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;
}

内部循环与前一个简单循环完全相同，您可以在某种程度上压缩代码，但是这段代码显示了解决设计问题时应该采取的方法。分析您可能有哪些不同的场景来解决每个场景，然后您可能能够同时解决几个场景(例如，有第三个场景可以删除最后一个元素，但是与上面的第二个场景一起解决)

Answer 2

提示:这是删除前的列表的一部分：

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

这是删除后的列表的一部分：

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

如您所见，更改前一个节点的Next引用就足够了。

(由于这显然是一个家庭作业或培训问题-我看不出重新实现C#中的链表的另一个原因--这应该足以使您走上正确的轨道。)

提示2：

• 在迭代列表时，保持对前一个节点和当前节点的引用(这是循环体中的一个简单的C#分配)。
• 在找到一些内容之后，更新前一个节点的Next引用(这也是一个简单的C#分配)。
• 移除第一个元素需要特别注意，但是让我们在算法的其余部分工作之后处理这个问题。