1. Introduction

In linked lists, deleting a node is a fundamental operation. However, a variant of this operation is to delete the last occurrence of a specific value. This requires a traversal of the list to locate the last occurrence and then a modification of the appropriate pointers to remove that node.

2. Program Steps

1. Initialize three pointers: current, prev, and lastOccurrence.

2. Traverse through the linked list using the current pointer.

3. If the current node’s data matches the target data, update the lastOccurrence pointer to the current node and the prev pointer to the previous node.

4. Continue this until the end of the list.

5. If lastOccurrence is not null (indicating that the target data was found), modify the pointers to delete the node.

6. Handle edge cases where the target data might be at the head or elsewhere in the list.

3. Code Program

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Function to delete the last occurrence of a given node
    public void deleteLastOccurrence(int key) {
        Node current = head;
        Node prev = null;
        Node lastOccurrence = null, prevLastOccurrence = null;

        // Traverse through the list
        while (current != null) {
            // If node with data equal to key is found, update pointers
            if (current.data == key) {
                lastOccurrence = current;
                prevLastOccurrence = prev;
            }
            prev = current;
            current = current.next;
        }

        // If key was present in linked list, remove the last occurrence
        if (lastOccurrence != null) {
            if (lastOccurrence == head) {
                head = head.next;
            } else {
                prevLastOccurrence.next = lastOccurrence.next;
            }
        }
    }

    // Function to print the linked list
    void printList() {
        Node n = head;
        while (n != null) {
            System.out.print(n.data + " ");
            n = n.next;
        }
    }

    // Function to insert a new Node at the last
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.append(1);
        list.append(2);
        list.append(3);
        list.append(2);
        list.append(5);

        System.out.println("Original Linked list:");
        list.printList();

        list.deleteLastOccurrence(2);

        System.out.println("\nLinked list after deleting last occurrence of 2:");
        list.printList();
    }
}

Output:

Original Linked list:
1 2 3 2 5
Linked list after deleting last occurrence of 2:
1 2 3 5

4. Step By Step Explanation

1. A Node class is defined to create new nodes for the Linked List. Each node has a data value and a next pointer which points to the subsequent node.

2. The LinkedList class provides methods to manipulate the linked list, including the deleteLastOccurrence method.

3. The deleteLastOccurrence method traverses the list and keeps track of the last node with the target value using the lastOccurrence pointer.

4. After the traversal, if the lastOccurrence is not null, it means the target data was found in the list, and its last occurrence is removed by modifying the appropriate pointers.

5. In the main method:

a. A LinkedList object is created.

b. Nodes with values 1, 2, 3, 2, 5 are added to the list.

c. The original list is printed.

d. The last occurrence of 2 is deleted from the list.

e. The updated list is printed.

Being able to delete specific nodes from a Linked List based on certain conditions is a common task in various applications and is frequently encountered in coding challenges.