从链接列表中删除最大值

Question

所以我在标题中说过，我想从LinkedList中删除最大的值，但我不知道该怎么做。我试过了，但遇到了一个错误。

//Remove n from list 'first'
public static void Remove(Node<int> first, Node<int> n)
{
Node<int> pos = first;
while (pos.GetNext() != n)
pos = pos.GetNext();
pos.SetNext(n.GetNext());
}
public static void DeleteMaxValue(Node<int> first)
{
int max = 0;
Node<int> pos = first;
Node<int> maxNode = null;
while(pos.GetNext() != null)
{
if (pos.GetNext().GetValue() > max)
{
maxNode = new Node<int>(pos.GetNext().GetValue());
}
pos = pos.GetNext();
}
Remove(first, maxNode);
}

Answer 1

假设这是链接列表中的节点结构

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

你可以使用这个功能来找到链接列表中最大的数字，然后将其删除。

public int GetMax(Node head)
{
int max = int.MinValue();
while(head != null)
{
if(max < head.data)
max = head.data;
head = head.next;
}
return max;
}

Answer 2

几个问题：

• max从不更新。当您找到一个更大的值时，应该更新它，否则最后一个正值被认为是最大的。

• maxNode从来都不是列表中的节点，因为它是作为新节点创建的。因此，Remove函数将找不到它，并且不会删除任何内容。

• 函数的签名无法删除第一个节点，因为first是通过值传递的。没有办法解决所有情况下的问题，除非你改变设计：

  • 要么让first成为类的成员，然后不要将其作为参数传递，或者
  • 让函数返回(可能(first的新值，这样调用者就可以将自己的引用调整为列表的开头

• max = 0假定您的列表不能有负值。如果这是可能的，我建议用第一个节点中的值初始化max(在检查列表不为空之后(。

• 与其使用Remove再次循环浏览列表，不如保留对要删除的节点之前的节点的引用。

这里有一个函数，返回first的值，因此调用方可以在第一个节点被删除的情况下更新自己的引用：

// Return type changed: the function will return the first node
public static Node<int> DeleteMaxValue(Node<int> first)
{
if (first == null) { // In an empty list there is nothing to delete
return;
}
int max = first.GetValue(); // Don't use 0, values might be negative
Node<int> pos = first;
Node<int> maxNode = first;
Node<int> beforeMaxNode = null;  // Have a reference that lags behind
while(pos.GetNext() != null)
{
int val = pos.GetNext().GetValue();
if (val > max)
{
max = val; // Update max
beforeMaxNode = pos; // Don't create a new node
}
pos = pos.GetNext();
}
if (beforeMaxNode == null) { // First node has the maximum
// Now `first` reference will change, so it's important to return 
//    that new reference, else the caller will not see any change
first = maxNode.GetNext();
} else {
beforeMaxNode.SetNext(maxNode.GetNext());
}
return first;
}