Here are the class definitions of Node and List that impleme

Here are the class definitions of Node and List that implement a linked list.

class Node {

private Node next;

private int key;

Node(Node nxt, int keyValue); // constructor

Node getNext();

int getKey();

void putNext(Node nxt);

}

class List { // assume the class does not use a dummy Node

private Node head;

List(); // constructor

boolean exists(int ky); // returns true if v is in the list

void insertAtHead(int ky); // inserts at the beginning of the list

void insertAtTail(int ky); // inserts at the end of the list

int removeFromHead(); // Returns -1 if the list is empty

void delete(int ky); // delete the element or do nothing if v doesn’t exist

int removeSmallest(); // removes the Node containing the smallest key and returns that key. Returns -1 if the list is empty. Could be duplicate entries, so remove the first

int removeLargest(); // removes the Node containing the largest key and returns that key. Returns -1 if the list is empty. Could be duplicate entries, so remove the first

int maxElement(); // calls the private version, doesn’t delete the

Node int sum(); // calls the private version

int length(); // calls the private version private

int maxElement(Node x); private int sum(Node x); private int length(Node x);

}

1. Assume the addition of the two functions:

public void recursiveDelete(int ky) {

// calls the private version

}

private Node recursiveDelete(int ky, Node n);

Write both functions.

Solution

After seeing the question, I think you are looking for
deleting a Node from Linked List recursively.

Here is the code for the same.

public void recursiveDelete(int ky) {
   // check if the head is null
   if(head == null)
       return;
  
   // if head is not null, start recursiveDelete
   recursiveDelete(ky, head);
}

private Node recursiveDelete(int ky, Node n){

   // See if we are at end of list
   if(n == null)
       return null;
      
   // Check to see if current node is one to be deleted
   if(n.data == ky){
       // Save the next pointer in the node
       Node temp = n.next;
      
       // Deallocate the node.
       n = null;
      
       // Return the NEW pointer to where we were called from. i.e., the pointer to the next node of the skipped node.
       return temp.next;
   }
  
   // Check the rest of the list, fixing the next pointer in case the next node is the one removed.
   n.next = recursiveDelete(ky, n.next);
  
   // Return the pointer to where we were called from.
   return n;
}