1

int value我知道如何使用 while 循环遍历单个链表的节点，但是如果它们的值匹配，我该如何删除某些节点头缠着这个。

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 的节点将被删除。

4

2 回答 2

3

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

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

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

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

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

（因为这显然是一个家庭作业或培训问题——我看不出在 C# 中重新实现链表的另一个原因——这应该足以让你走上正轨。）

提示2：

  • 遍历列表时，保留对前一个节点和当前节点的引用（这是循环体内的一个简单 C# 赋值）。
  • 找到某些内容后，更新前一个节点的Next引用（这也是一个简单的 C# 赋值）。
  • 删除第一个元素需要特别小心，但让我们在算法的其余部分工作后处理它。
于 2013-10-16T07:36:38.640 回答
0

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

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

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

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

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

于 2013-10-16T07:59:29.907 回答