How to remove largest item from a Linear Linked List

[rylarson]

so here is my problem, I need to remove the largest integer from a linear linked list only traversing it once, I need to do this iteratively.

I believe this code works, it identifies the biggest number by comparing the two nodes together and the "big_delete" pointer just follows the biggest number, stopping when it reaches the biggest. Correct me if I am wrong on this.

Its the deallocation of memory and connecting the lists back together I am having trouble with.

Int first = 0;
Int second = 0;
Int biggest = 0;

Node * current;
			Node * temp;
			Node * big_delete;

Current = head->next;
			Temp = head;

			

			While(current) //while current is not null
			{
				First = temp->int;
				Second = current->int;
			
				If (first > second && first > biggest)
				{
					Biggest = first;
					Big_delete = temp;
				}
				Else if (second > first && second > biggest)
				{
					Biggest = second;
					Big_delete = current
				}
				Else
					Return;
				
				Current = current->next;
				Temp = temp->next;
			}
			
			Temp = head;
			Head = big_delete;	
			Delete head;
			Head = temp;
			
			Temp = NULL;
			Big_delete = NULL;			
			Current = NULL;

[Duthomhas]

You are trying to do too many things at once, and getting overloaded.

In all computing, you need to break a problem down into the simplest tasks possible. Given your assignment, you can reword it this way:

  1. Find the node containing the largest value in the list (traversing the list at most one time)
  2. Remove (unlink and delete) the node found in step one.

To find the biggest node, you only need a few things. Here's a start:

Node * find_largest_node( Node * head )
// Return the node in the list containing the largest value
// Returns NULL if head == NULL
{
    Node * largest = head;
    Node * current = head;  // Not head->next; this way allows head to be NULL 

    while (current)
    {
        ...
    }

    return largest;
}

Now you can use it to find the node containing the largest value. Once found, you can delete it. You should already have a function that deletes a node from your list. It should look something like this:

Node * delete_node( Node * head, Node * to_delete )
// Delete a node from the list
// Returns the new head of the list
// (which may change if to_delete == head)
{
    if (head != NULL)
    {
        ...
    }
    return head;
}

Your final code should then look something like this:

// Here is a list
Node * my_list = NULL;

// Populate the list here
...

// Delete the largest value in the list
my_list = delete_node( my_list, find_largest_node( my_list ) );

Once you have that working, there is one more (trivial) thing to consider about the find_largest_node() function: if more than one node has the largest value, which is returned: the first or the last?

Hope this helps.

[edit] Fixed typos...