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