I need help with this java program, it is already been done need few changes to
ID: 3856566 • Letter: I
Question
I need help with this java program, it is already been done need few changes to it. i am providing the program needed for this.
Question needs to be solved:
implement a function to check if a linked list is a palindrome.
--------------------------------------------------------------------------------------------------------------
Driver.java
//import ch06.lists.*;
//import support.*;
public class Driver
{
public static void main(String[] args)
{ //page 469 #51
System.out.println("page 469 #51 testing removeAll() ");
RefUnsortedList<String> myList;
myList = new RefUnsortedList<String>();
myList.add("3");
myList.add("4");
myList.add("3");
myList.add("5");
myList.add("3");
myList.add("6");
myList.add("3");
myList.add("3");
myList.add("7");
System.out.println("myList: "+myList);
myList.removeAll1("3");
System.out.println("myList: "+myList);
}
}
-------------------------------------------------------------------------------------------------------------------------------------------
LLNode.java
class LLNode<T>
{
private T info;
private LLNode<T> next;
public void setLink(LLNode<T> node)
{
next = node;
}
public LLNode<T> getLink()
{
return next;
}
public LLNode(T inf)
{
info = inf;
}
public T getInfo()
{
return info;
}
}
class RefUnsortedList<T>
{
protected int numElements;
protected LLNode<T> currentPos;
protected boolean found;
protected LLNode<T> location;
protected LLNode<T> previous;
protected LLNode<T> list;
public RefUnsortedList()
{
numElements = 0;
list = null;
currentPos = null;
}
public void add(T element)
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(list);
list = newNode;
numElements++;
}
protected void find(T target)
{
location = list;
found = false;
while (location != null)
{
if (location.getInfo().equals(target))
{
found = true;
return;
}
else
{
previous = location;
location = location.getLink();
}
}
}
public int removeAll1(T target)
{
location = list;
found = false;
int cnt=0;
while (location.getLink() != null)
{
if (location.getLink().getInfo().equals(target))
{
location.setLink(location.getLink().getLink());
cnt++;
}
else
{
location = location.getLink();
}
}
if(list.getInfo().equals(target))
{
list = list.getLink();
cnt++;
}
return cnt;
}
public int size()
{
return numElements;
}
public boolean contains (T element)
{
find(element);
return found;
}
public boolean remove (T element)
{
find(element);
if (found)
{
if (list == location)
list = list.getLink();
else
previous.setLink(location.getLink());
numElements--;
}
return found;
}
public int removeAll(T ele)
{
int count =0;
while(remove(ele))
count++;
return count;
}
public T get(T element)
{
find(element);
if (found)
return location.getInfo();
else
return null;
}
public String toString()
{
LLNode<T> currNode = list;
String listString =" List:";
while (currNode != null)
{
listString = listString + " " + currNode.getInfo() + " ";
currNode = currNode.getLink();
}
return listString;
}
public void reset()
{
currentPos = list;
}
public T getNext()
{
T next = currentPos.getInfo();
if (currentPos.getLink() == null)
currentPos = list;
else
currentPos = currentPos.getLink();
return next;
}
}
Explanation / Answer
HI below is your code to check for Palindrome. I have changed the dtiver function also to test. PLease let me know if its fine or you need something else.
LLNode.java
class LLNode<T> {
private T info;
private LLNode<T> next;
public void setLink(LLNode<T> node) {
next = node;
}
public LLNode<T> getLink() {
return next;
}
public LLNode(T inf) {
info = inf;
}
public T getInfo() {
return info;
}
}
class RefUnsortedList<T> {
protected int numElements;
protected LLNode<T> currentPos;
protected boolean found;
protected LLNode<T> location;
protected LLNode<T> previous;
protected LLNode<T> list;
LLNode<T> slow_ptr, fast_ptr, second_half;
public RefUnsortedList() {
numElements = 0;
list = null;
currentPos = null;
}
public void add(T element) {
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(list);
list = newNode;
numElements++;
}
protected void find(T target) {
location = list;
found = false;
while (location != null) {
if (location.getInfo().equals(target)) {
found = true;
return;
} else {
previous = location;
location = location.getLink();
}
}
}
public int removeAll1(T target) {
location = list;
found = false;
int cnt = 0;
while (location.getLink() != null) {
if (location.getLink().getInfo().equals(target)) {
location.setLink(location.getLink().getLink());
cnt++;
} else {
location = location.getLink();
}
}
if (list.getInfo().equals(target)) {
list = list.getLink();
cnt++;
}
return cnt;
}
public int size() {
return numElements;
}
public boolean contains(T element) {
find(element);
return found;
}
public boolean remove(T element) {
find(element);
if (found) {
if (list == location)
list = list.getLink();
else
previous.setLink(location.getLink());
numElements--;
}
return found;
}
public int removeAll(T ele) {
int count = 0;
while (remove(ele))
count++;
return count;
}
public T get(T element) {
find(element);
if (found)
return location.getInfo();
else
return null;
}
public String toString() {
LLNode<T> currNode = list;
String listString = " List:";
while (currNode != null) {
listString = listString + " " + currNode.getInfo() + " ";
currNode = currNode.getLink();
}
return listString;
}
public void reset() {
currentPos = list;
}
public T getNext() {
T next = currentPos.getInfo();
if (currentPos.getLink() == null)
currentPos = list;
else
currentPos = currentPos.getLink();
return next;
}
/* Function to check if two input lists have same data */
boolean compareLists(LLNode<T> head1, LLNode<T> head2) {
LLNode<T> temp1 = head1;
LLNode<T> temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.getInfo() == temp2.getInfo()) {
temp1 = temp1.getLink();
temp2 = temp2.getLink();
} else
return false;
}
/* Both are empty rerun */
if (temp1 == null && temp2 == null)
return true;
/*
* Will reach here when one is NULL and other is not
*/
return false;
}
/*
* Function to check if given linked list is palindrome or not
*/
boolean isPalindrome(LLNode<T> head) {
slow_ptr = head;
fast_ptr = head;
LLNode<T> prev_of_slow_ptr = head;
LLNode<T> midnode = null; // To handle odd size list
boolean res = true; // initialize result
if (head != null && head.getLink() != null) {
/*
* Get the middle of the list. Move slow_ptr by 1 and fast_ptrr by
* 2, slow_ptr will have the middle node
*/
while (fast_ptr != null && fast_ptr.getLink() != null) {
fast_ptr = fast_ptr.getLink().getLink();
/*
* We need previous of the slow_ptr for linked lists with odd
* elements
*/
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr.getLink();
}
/*
* fast_ptr would become NULL when there are even elements in the
* list and not NULL for odd elements. We need to skip the middle
* node for odd case and store it somewhere so that we can restore
* the original list
*/
if (fast_ptr != null) {
midnode = slow_ptr;
slow_ptr = slow_ptr.getLink();
}
// Now reverse the second half and compare it with first half
second_half = slow_ptr;
prev_of_slow_ptr.setLink(null); // NULL terminate first half
reverse(); // Reverse the second half
res = compareLists(head, second_half); // compare
/* Construct the original list back */
reverse(); // Reverse the second half again
if (midnode != null) {
// If there was a mid node (odd size case) which
// was not part of either first half or second half.
prev_of_slow_ptr.setLink(midnode);
prev_of_slow_ptr.setLink(second_half);
} else
prev_of_slow_ptr.setLink(second_half);
}
return res;
}
/*
* Function to reverse the linked list Note that this function may change
* the head
*/
void reverse() {
LLNode<T> prev = null;
LLNode<T> current = second_half;
LLNode<T> next;
while (current != null) {
next = current.getLink();
current.setLink(prev);
prev = current;
current = next;
}
second_half = prev;
}
}
Driver.java
public class Driver {
public static void main(String[] args) { // page 469 #51
System.out.println("page 469 #51 testing removeAll() ");
RefUnsortedList<String> myList;
myList = new RefUnsortedList<String>();
myList.add("3");
myList.add("4");
myList.add("3");
myList.add("5");
myList.add("3");
myList.add("6");
myList.add("3");
myList.add("3");
myList.add("7");
System.out.println("myList: " + myList);
myList.removeAll1("3");
System.out.println("myList: " + myList);
RefUnsortedList<String> myList2;
myList2 = new RefUnsortedList<String>();
myList2.add("1");
myList2.add("2");
myList2.add("1");
myList2.add("2");
myList2.add("1");
System.out.println("List 1: "+myList);
System.out.println("List 2: "+myList2);
if(myList.isPalindrome(myList.list)) {
System.out.println("List 1 is palindrome. ");
} else {
System.out.println("List 1 is not palindrome.");
}
if(myList2.isPalindrome(myList2.list)) {
System.out.println("List 2 is palindrome. ");
} else {
System.out.println("List 2 is not palindrome.");
}
}
}
Sample Output: -
page 469 #51 testing removeAll()
myList: List: 7 3 3 6 3 5 3 4 3
myList: List: 7 6 5 4
List 1: List: 7 6 5 4
List 2: List: 1 2 1 2 1
List 1 is not palindrome.
List 2 is palindrome.