Question

You are asked to delete the last occurrence of an item from a linked list. So, for instance:

Input: 2 -> 3 -> 2 -> 4

Delete last occurrence of 2, result: 2 -> 3 -> 4

Implement the following method to do the deletion. You may NOT use or implement helper methods - all your code must be implemented inside the given method. You may NOT use recursion.

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

// Deletes LAST occurrence of given item from a linked list,
// given a front pointer to the first node in the list.
// Returns pointer to first node of the updated linked list.
// Input list could be empty.
// Throws NoSuchElementException if item is not in the linked
// list.

public static Node deleteLastOccurrence(Node front, int item)
throws NoSuchElementException {

// COMPLETE THIS METHOD

}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

//required method
public static Node deleteLastOccurrence(Node front, int item)
                throws NoSuchElementException {
        // initializing a boolean flag to false
        boolean found = false;
        // two Node references, one to store previous node of current node under
        // process, and other is to store previous of the target node if found.
        Node prev = null, prevTarget = null;
        // looping through each node
        for (Node n = front; n != null; n = n.next) {
                // checking if this node contains item
                if (n.data == item) {
                        // setting current prev node as prevTarget
                        prevTarget = prev;
                        // setting flag to true
                        found = true;
                        // useful tip: add a break; statement here if you want to remove
                        // the first occurrence instead.
                }
                // setting n as new prev
                prev = n;
        }
        // now if found is false throwing NoSuchElementException
        if (!found) {
                throw new NoSuchElementException();
        }
        // otherwise if prevTarget is null, that means we have to remove front
        // node
        if (prevTarget == null) {
                front = front.next; // advancing front
        } else {
                // otherwise removing node between prevTarget and
                // prevTarget.next.next
                prevTarget.next = prevTarget.next.next;
        }
        // returning front node
        return front;
}