循环访问链表以删除节点

本文关键字：删除 节点 链表 访问 循环 | 更新日期: 2023-09-27 18:35:38

我知道如何使用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，则列表变为 7、8、9、3、2，因为具有 5 的节点将被删除。

循环访问链表以删除节点

提示：这是删除前的列表（部分）：

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

这是删除后的列表（部分）：

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

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

（由于这显然是一个家庭作业或训练问题 - 我看不出在C#中重新实现链表的其他原因 - 这应该足以让你走上正确的轨道。

提示2：

    循环
  • 访问列表时，请保留对上一个节点和当前节点的引用（这是循环体内的一个简单的 C# 赋值）。
  • 找到某些内容后，更新上一个节点的Next引用（这也是一个简单的 C# 赋值）。
  • 删除第一个元素需要特别小心，但让我们在算法的其余部分工作后再处理。

你应该看看你可能结束的情况。有两种主要删除方案

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

您的实现需要处理这两个问题。处理第一个很简单。您只需迭代传递具有给定值的前导元素

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

内部循环的功能与之前的简单循环完全相同，您可以稍微压缩代码，但是此代码显示了在解决设计问题时应采用的方法。分析您可能拥有哪些不同的场景来解决每个场景，然后您可能能够同时解决多个场景（例如，有第三种方案删除最后一个元素，但与上述第二个场景一起解决）

相关文章：