I need the java code only please... Using a Linked List structure, determine whe

Question

I need the java code only please...

Using a Linked List structure, determine whether a linked list contains a Palindrome in integers. For example, the following is a Palindrome:

0-> 1 -> 2 -> 1 -> 0

To solve this problem, following these steps:

1.) reverse the linked list

2.) compare the reversed list to the original list

3.) if they're the same, you have a Palindrome.

Create the following methods in a driver class, and call them from main:

boolean isPalindrome(LinkedListNode head) ~ given the starting node of a linked list, will return whether the linked list is a Palindrome.

LinkedListNode reverseAndClone(LinkedListNode node) ~ given the starting node of a linked list, will return the starting node of the reversed linked list.

boolean isEqual(LinkedListNode one, LinkedListNode two) ~ given the starting node of 2 linked lists, will return whether they are both the same.

Define 2 global linkedList variables that can be accessed from anywhere, one for origLinkedList and the other for reversedLinkedList.

To test the program, in main method:

1. create a linked list that is a Palindrome, and call the isPalindrome method. Test to ensure it returns True.
2. create a linked list that is NOT a Palindrome, and ensure the call to isPalindrome returns a False.

Explanation / Answer

/* Java program to check if linked list is palindrome */

class LinkedList
{
Node head; // head of list
Node slow_ptr, fast_ptr,second_half;

/* Linked list Node*/
class Node
{
char data;
Node next;

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

/* Function to check if given linked list is
palindrome or not */
boolean isPalindrome(Node head)
{
slow_ptr = head; fast_ptr = head;
Node prev_of_slow_ptr = head;
Node midnode = null; // To handle odd size list
boolean res = true; // initialize result

if (head != null && head.next != 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.next != null)
{
fast_ptr = fast_ptr.next.next;

/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr.next;
}

/* 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.next;
}

// Now reverse the second half and compare it with first half
second_half = slow_ptr;
prev_of_slow_ptr.next = 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.next = midnode;
midnode.next = second_half;
} else
prev_of_slow_ptr.next = second_half;
}
return res;
}

/* Function to reverse the linked list Note that this
function may change the head */
void reverse()
{
Node prev = null;
Node current = second_half;
Node next;
while (current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
second_half = prev;
}

/* Function to check if two input lists have same data*/
boolean compareLists(Node head1, Node head2)
{
Node temp1 = head1;
Node temp2 = head2;

while (temp1 != null && temp2 != null)
{
if (temp1.data == temp2.data)
{
temp1 = temp1.next;
temp2 = temp2.next;
} else
return false;
}

/* Both are empty reurn 1*/
if (temp1 == null && temp2 == null)
return true;

/* Will reach here when one is NULL
and other is not */
return false;
}

/* Push a node to linked list. Note that this function
changes the head */
public void push(char new_data)
{
/* Allocate the Node &
Put in the data */
Node new_node = new Node(new_data);

/* link the old list off the new one */
new_node.next = head;

/* Move the head to point to new Node */
head = new_node;
}

// A utility function to print a given linked list
void printList(Node ptr)
{
while (ptr != null)
{
System.out.print(ptr.data + "->");
ptr = ptr.next;
}
System.out.println("NULL");
}

/* Driver program to test the above functions */
public static void main(String[] args) {

/* Start with the empty list */
LinkedList llist = new LinkedList();

char str[] = {'a', 'b', 'a', 'c', 'a', 'b', 'a'};
String string = new String(str);
for (int i = 0; i< 7 ; i++) {
llist.push(str[i]);
llist.printList(llist.head);
if (llist.isPalindrome(llist.head) != false)
{
System.out.println("Is Palindrome");
System.out.println("");
}
else
{
System.out.println("Not Palindrome");
System.out.println("");
}
}
}
}

sample Output:
a->NULL
Palindrome

b->a->NULL
Not Palindrome

a->b->a->NULL
Is Palindrome

c->a->b->a->NULL
Not Palindrome

a->c->a->b->a->NULL
Not Palindrome

b->a->c->a->b->a->NULL
Not Palindrome

a->b->a->c->a->b->a->NULL
Is Palindrome

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.