Remove the biggest value from a linked list

Question

So I've said it in the title, I want to delete the biggest value from a LinkedList, can't get my head around how to exactly do it. I tried this but I get an error.

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

Kinda wasteful though isn't it, to enumerate the list looking for the max, then enumerate again looking for the previous-one-before-max just so you can zip from the previous to the max.next, cutting out the max.. if you keep track of the previous-to-max node instead of the max node you can do the remove with one enumeration rather than two — Caius Jard, Jan 06 '22 at 20:07
You might want to update your `max` value at some point? Also, unless you've done something to ensure two different instances are comparable, making a new node for the max won't work, because that particular node it's not actually a member of the list so Remove will never find it — Caius Jard, Jan 06 '22 at 20:08
So how would you go about doing that? I need a way to get a refrenece to a node instead of it's value, I'm not sure if you can do that? — Brist, Jan 06 '22 at 20:18
This should not have been closed, since a NullReferenceException is not the issue in the question, but just an error caused by the actual problem OP has. Voted to reopen. — Bent Tranberg, Jan 06 '22 at 20:21
`pos` is looking like it's intended to be always a "reference to the node before the max". If you were to do `maxNode = pos` (and rename maxNode to "nodeBeforeMax") you'd be "saving a reference" to an actual node in the list. Don't forget to update `max` integer, or get rid of max integer and get highest via nodeBeforeMax.Next.Value (but if the first node is the true max; you either actually need to create a fake node to initialize nodeBeforeMax to so the fake node's next can be the first in the list or you need to special case check the first node against the found max before you delete ..) — Caius Jard, Jan 06 '22 at 20:34
As with any trivial/contrived/academic programming task, if the language is new to you you really really should write the algorithm out in comments in your native language first and then translate to code underneath the comments. It's exactly the same as writing an essay plan before you write the essay — Caius Jard, Jan 06 '22 at 20:37
This worked! I saved a reference to nodebeforemax and removed the one after. Thanks — Brist, Jan 06 '22 at 20:56

score 0 · Answer 1 · answered Jan 06 '22 at 21:29

imagine this is your Node structure in linked list

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

you can use this function to find the biggest number in the linked list and then remove it.

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

score 0 · Answer 2 · answered Jan 07 '22 at 07:38

Several issues:

max is never updated. It should be updated when you have found a greater value, otherwise the last positive value is considered the greatest.
maxNode is never a node that is in the list, since it is created as a new node. By consequence the Remove function will not find it and nothing gets deleted.
Your function's signature has no way of deleting the first node, since first is passed by value. There is no way to solve this for all cases, unless you change the design:
- Either let first be a member of your class, and then don't pass it as argument, or
- Let the function return the (potentially) new value of first, so the caller can adapt its own reference to the head of the list.
max = 0 assumes that your list cannot have negative values. In case this is possible, I would suggest initialising max with the value that is in the first node (after having checked that the list is not empty).
Instead of cycling again through the list with Remove, keep a reference to the node the precedes the node that is to be deleted.

Here is a function that returns the value of first, so the caller can make an update to their own reference in case the first node was deleted:

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

Remove the biggest value from a linked list

2 Answers2