HW1.1 asked for a function that would "delete the largest element from an unordered
linked list".
Several people had a function prototype similar to
this:
void deleteLargest(LLNode head)
And the function might be something like:
public void deleteLargest(LLNode head)
{
if ( null == head )
return;
LLNode p = head;
LLNode prev = null;
LLNode max = head;
LLNode maxPrev = null;
while ( null != p )
{
if ( p.val > max.val )
{
max = p;
maxPrev = prev;
}
prev = p;
p = p.next;
}
//remove the maxNode
if ( null == maxPrev )
head = head.next;
else
maxPrev.next = maxNode.next;
}
Now, what's wrong with this code?! Is there anything wrong with it?
Give it a list [ 1, 2, 3] and it will correctly change it into [1, 2].
The question is: How will it deal with list [3, 2, 1] or with list [1]?
If the first element turns out to be the max, then 'head' will be reset to
'head.next'. But the caller of this function will have no way to notice this.
Say, you have some LList lis. Now you call the function:
deleteLargest(lis);
When this call is made, argument 'lis' is passed by value -- that is, a _copy_ of
pointer 'lis' (a copy of the pointer, not of the object pointed to!) is passed to the
function, and
this copy (called 'head') will be processed inside the function. Of course, in the
beginning, the
copy ('head') and the original pointer ('lis') refer to the same object. This means
that you can
make changes to the object inside this function. But resetting 'head' inside the
function will have
no impact whatsoever on the original list (as soon as you leave the function, 'head'
will be lost).
The upshot is that you cannot remove the max if the list has only one element, or if
max is the
first element.
How to correct this?
1. Make the function static, and let it return a LLNode:
public static LLNode deleteLargest(LLNode head) {
if (null==head)
return head;
// everything else same as above
return head;
}
Now, given a LLNode lis, you can call it as
lis = deleteLargest(lis);
2. Or, make 'head' a global variable, and give the function the signature
void deleteLargest() {
// same as above
}
In this case you would assume something like
class List {
LLNode head;
...
public void deleteLargest() {...}
}
Hans
