- Write a recursive method findPalindrome(SLL list) that finds whether the contents of a singly linked list form a palindrome. The algorithm is as follows:
- Base Case: If the list is empty or has one element, return true.
- Recursive Case: If the head and tail have the same contents, apply findPalindrome on a new, shorter list without the head and tail of the original list; if the head and tail do not have the same contents, return false.
Use the SLL.java and SLLNode.java given below: (Please show snapshots of working code and output)
////SLL.java////
public class SLL { protected SLLNode head, tail; public SLL() { head = tail = null; } public boolean isEmpty() { return head == null; } public void addToHead(T el) { head = new SLLNode(el,head); if (tail == null) tail = head; } public void addToTail(T el) { if (!isEmpty()) { tail.next = new SLLNode(el); tail = tail.next; } else head = tail = new SLLNode(el); } public T deleteFromHead() { // delete the head and return its info; if (isEmpty()) return null; T el = head.info; if (head == tail) // if only one node on the list; head = tail = null; else head = head.next; return el; } public T deleteFromTail() { // delete the tail and return its info; if (isEmpty()) return null; T el = tail.info; if (head == tail) // if only one node in the list; head = tail = null; else { // if more than one node in the list, SLLNode tmp; // find the predecessor of tail; for (tmp = head; tmp.next != tail; tmp = tmp.next); tail = tmp; // the predecessor of tail becomes tail; tail.next = null; } return el; } public void delete(T el) { // delete the node with an element el; if (!isEmpty()){ if (head == tail && el.equals(head.info)) // if only one head = tail = null; // node on the list; else if (el.equals(head.info)) // if more than one node on the list; head = head.next; // and el is in the head node; else { // if more than one node in the list SLLNode pred, tmp;// and el is in a nonhead node; for (pred = head, tmp = head.next; tmp != null && !tmp.info.equals(el); pred = pred.next, tmp = tmp.next); if (tmp != null) { // if el was found; pred.next = tmp.next; if (tmp == tail) // if el is in the last node; tail = pred; } else throw new IllegalArgumentException("Element not found."); } } else throw new UnsupportedOperationException("List is empty."); } public void printAll() { if(isEmpty()) throw new UnsupportedOperationException("List is empty."); SLLNode tmp; for (tmp = head; tmp.next != null; tmp = tmp.next) System.out.print(tmp.info + ", "); System.out.print(tmp.info); } public boolean isInList(T el) { SLLNode tmp; for (tmp = head; tmp != null && !tmp.info.equals(el); tmp = tmp.next); return tmp != null; } } /////SLLNode.java/////
public class SLLNode { public T info; public SLLNode next; public SLLNode() { this(null,null); } public SLLNode(T el) { this(el,null); } public SLLNode(T el, SLLNode ptr) { info = el; next = ptr; } }