Question

IN JAVA:

Implement an algorithm to check whether a LinkedList is a palindrome.

2 methods should be implemented:

1. Constant space, i.e. without creating extra copies of the linked list
2. Unrestricted space

q1:

/ For this implementation you should use constant space

  // Note: you are free to add any extra methods,

  // but this method has to be used

  public static boolean isPalindromeRestricted(ListNode head) {

    // Your code goes here

    return false;

  }

q2:

// For this implementation the space is not restricted

  // Note: you are free to add any extra methods,

  // but this method has to be used

  public static boolean isPalindromeUnrestricted(ListNode head) {

    // Your code goes here

    return false;

  }

Answer 1

A number is a palindrome if it reads the same forwards as it does backward. For example, the number 1233321 is a palindrome. Linked lists can also be palindromes if they have the same order of elements when traversed forwards and backward​.

Pseudocode to check whether the linked list is palindrome or not :

boolean isListPalindrome(ListNode head)
{
// if the linked list is empty or having only one node
if(head == NULL or head.next == NULL)
return True
stack <List Datatype> S
ListNode temp = head
// traversing the linked list and pushing the elements into stack
while(temp is not NULL)
{
S.push(temp.data)
temp=temp.next
}
temp = head
// again traversing the linked list to compare
while(temp is not NULL)
{
topOfStack = S.top()
S.pop()
if(topOfStack is not equal temp)
return False
temp=temp.next
}
return True
}

Algorithm :

• First, traverse the whole linked list, storing the value of each element in a stack at each step.
• Traverse the whole linked list again, this time popping out elements from the stack and comparing them with the elements in the linked list. If all the elements are the same, then the linked list is a palindrome.
• Traverse the given list from head to tail and push every visited node to stack.
• Traverse the list again. For every visited node, pop a node from stack and compare data of popped node with currently visited node.
• If all nodes matched, then return true, else false.

Java Program implementing isPalindromeRestricted() :

import java.util.*;

class LinkedList_Restricted
{
public static void main(String args[])
{
Node one = new Node('M');
Node two = new Node('A');
Node three = new Node('D');
Node four = new Node('A');
Node five = new Node('M');
one.ptr = two;
two.ptr = three;
three.ptr = four;
four.ptr = five;
boolean condition = isPalindromeRestricted(one);
System.out.println("isPalidrome :" + condition);
}
static boolean isPalindromeRestricted(Node head)
{
Node temp = head;
boolean ispalin = true;
Stack<Integer> stack = new Stack<Integer>();
while (temp != null)
{
stack.push(temp.data);
temp = temp.ptr;
}
while (head != null)
{
int i = stack.pop();
if (head.data == i)
{
ispalin = true;
}
else
{
ispalin = false;
break;
}
head = head.ptr;
}
return ispalin;
}
}
class Node
{
int data;
Node ptr;
Node(int d)
{
ptr = null;
data = d;
}
}

OUTPUT

Java Program implementing isPalindromeUnrestricted() :

class Linked_List_Unrestricted
{
Node head;
Node 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)
{
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 ptr by 1 and fast_ptr by 2, tr will have the middle node */
while (fast_ptr != null && fast_ptr.next != null)
{
fast_ptr = fast_ptr.next.next;
prev_of_slow_ptr = ptr;
ptr = ptr.next;
}
/* fast_ptr would become NULL when there are even elements in the list and not NULL for odd elements. */
if (fast_ptr != null)
{
midnode = ptr;
ptr = ptr.next;
}
//Reverse the second half and compare it with first half
second_half = ptr;
prev_of_slow_ptr.next = null;        // NULL terminate first half
reverse();                                                // Reverse the second half
res = compareLists(head, second_half);
                                                   // 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 */
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;
}
if (temp1 == null && temp2 == null)
return true;
       return false;
}

/* Push a node to linked list*/
public void push(char new_data)
{
Node new_node = new Node(new_data);
       new_node.next = head;
/* Move the head to point to new Node */
head = new_node;
}
// Print a given linked list
void printList(Node ptr)
{
while (ptr != null)
{
System.out.print(ptr.data + "->");
ptr = ptr.next;
}
System.out.println("NULL");
}
   public static void main(String[] args)
{
   Linked_List_Unrestricted LLU = new Linked_List_Unrestricted();
   char str[] = { 'M', 'A', 'L', 'A', 'Y', 'A', 'L','A','M' };
String string = new String(str);
for (int i = 0; i < 9; i++)
{
LLU.push(str[i]);
LLU.printList(LLU.head);

}
if (LLU.isPalindrome(LLU.head) != false)
       {
       System.out.println("Is Palindrome");
       System.out.println("");
       }
       else
       {
       System.out.println("Not Palindrome");
       System.out.println("");
}
}
}
OUTPUT