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

code:

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

// Linked list Node
class LinkedListNode
{
protected int data;
protected LinkedListNode next;

public LinkedListNode(int num)
{
data = num;
next = null;
}
// constructor
public LinkedListNode()
{
data = 0;
next = null;
}
}

class LinkedList
{
protected LinkedListNode head; // head of list
// constructor
public LinkedList()
{
head = null;
}
  
// Push a node to linked list. Note that this function changes the head
public void push(int new_data)
{
// Allocate the Node & Put in the data
LinkedListNode new_node = new LinkedListNode(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;
}
}
// Driver program to test
public class driver
{
static LinkedListNode bkNode; // creating a backup node for linked list as per your desired arguments for functions
// Function to check if given linked list is palindrome or not
static boolean isPalindrome(LinkedListNode head)
{
boolean res = true; // initialize result
LinkedList reversedLinkedList = new LinkedList();
LinkedListNode temp = head;
reversedLinkedList.head = reverseAndClone(temp);
res = isEqual(bkNode, reversedLinkedList.head);
return res;
}

// Function to reverse the linked list Note that this function may change the head
static LinkedListNode reverseAndClone(LinkedListNode head)
{
if(head == null || head.next == null)
return head;

LinkedListNode rev = head;
LinkedListNode orig = rev.next;

head.next = null;
while(rev != null && orig != null){
LinkedListNode temp = orig.next;
orig.next = rev;
rev = orig;
orig = temp;
}

return rev;
}

// Function to check if two input lists have same data
static boolean isEqual(LinkedListNode one, LinkedListNode two)
{
LinkedListNode orig = one, rev = two;
while (orig != null && rev != null)
{
if (orig.data != rev.data)
return false;

// If we reach here, then orig and rev are not null and their data is same, so move to next nodes in both lists
orig = orig.next;
rev = rev.next;
}

// If linked lists are identical, then 'orig' and 'rev' must be null at this point.
return (orig == null && rev == null);
}
  
public static void main(String[] args)
{
/* Start with the empty list */
LinkedList origLinkedList = new LinkedList();
LinkedList bkLinkedList = new LinkedList(); // Creating a backup linked list because node is tampered during operations.
int arr[] = {0,1,0,1,0};
for (int i = 0; i< arr.length ; i++) {
origLinkedList.push(arr[i]);
bkLinkedList.push(arr[i]);
}
bkNode = bkLinkedList.head;
if (isPalindrome(origLinkedList.head) != false)
{
System.out.println("");
System.out.println("Is Palindrome");
System.out.println("");
}
else
{
System.out.println("");
System.out.println("Not Palindrome");
System.out.println("");
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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