Question

Need the answers to these RECURSIVE practice problems using Linked Lists in JAVA . Thank you.

Complete the Link class by writing methods described below. Do not use loops, or create any more methods (other than those specified), class or instance variables. public class Link private Link next; /null if this is the last link private int value; public Link(Link n, int v) nextn valuev; Do not use loops, or create any more methods (other than those specified), class or instance variables. 1. Write a recursive instance method count that takes no parameters and returns an int. Return the number of links that hold the value zero, with the exception that the last link in the list is not included in the count. For example, for the linked list, {(first) 5→0→3→1→0→0 (last)) it would return the value 2. 2. Write a recursive instance method isSorted that takes a Link parameter and determines whether a linked list is sorted in descending order or not (retun a boolean value). 3. Write a recursive instance method named findBad that takes no parameters and returns a reference to a Link. The result of calling findBad is a reference to the first link that has a value greater than the next link's value. If no such link exists return null. For example, for {5→6→7→3→2) it would return a reference to the third link ("7").

Answer 1

//Java program

class Link{
   private Link next;
   private int value;
  
   public Link(Link n , int v) {
       next = n;
       value = v;
   }
   public Link getNext() {
       return next;
   }
   public void setNext(Link n) {
       next = n;
   }
   public int getValue() {
       return value;
   }
   public void setValue(int v) {
       value = v;
   }
}
class LinkList{
   private Link head;
  
   private int countRec(Link node) {
       if(node==null||node.getNext()==null)return 0;
       if(node.getValue()==0)return 1 + countRec(node.getNext());
       else return countRec(node.getNext());
      
   }
   private Link findBadRec(Link node) {
       if(node==null||node.getNext()==null)return null;
       if(node.getValue()>node.getNext().getValue())return node;
       else return findBadRec(node.getNext());
   }

  
   public LinkList() {
       head = null;
   }
   public void append(int data) {
       Link node = new Link(null,data);
       if(head==null) {
           head = node;
           return;
       }
       Link current = head;
       while(current.getNext()!=null)current = current.getNext();
       current.setNext(node);
   }
  
   public void print() {
       Link current = head;
       while(current!=null) {
           System.out.print(current.getValue()+" ");
           current = current.getNext();
       }
       System.out.println();
   }
  
   public int count() {
       return countRec(head);
   }
  
   public Link findBad() {
       return findBadRec(head);
   }
  
}

public class LinkedListt {
   public static void main(String args[]) {
       LinkList list = new LinkList();
       list.append(5);
       list.append(6);
       list.append(7);
       list.append(3);
       list.append(2);
      
       System.out.println(list.findBad().getValue());
      
      
   }
  
   public static boolean isSorted(Link node) {
       if(node==null||node.getNext()==null)return true;
       if(node.getValue()>=node.getNext().getValue())return isSorted(node.getNext());
       return false;
   }
}