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​.

# 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.


# Implementation
The following code implements the above algorithm.

#include<bits/stdc++.h> 
using namespace std;  
  
class Node { 
public: 
  int data;

  Node(int d){ 
    data = d; 
  } 
  Node *ptr; 
}; 
  
bool isPalindrome(Node* head){ 
  // This pointer will allow the first traversal
  // of the linked list
  Node* next= head;   
  // Declare a stack  
  stack <int> s; 

  // Traverse the linked list and add its elements
  // to the stack
  while(next != NULL){ 
    s.push(next->data); 
    next = next->ptr; 
  } 

  // Iterate the linked list again and  
  // check by each element with the stack 
  while(head != NULL ){      
    int i=s.top(); 

    if(head -> data != i){ 
      return false; 
    }
    // Move to the next element in stack and the list 
    s.pop(); 
    head=head->ptr; 
  } 

return true; 
} 
  
// Driver Code  
int main(){ 

  Node one =  Node(1); 
  Node two = Node(3); 
  Node three = Node(5); 
  Node four = Node(3); 
  Node five = Node(1); 

  // Initialize the pointers of the Linked List
  five.ptr = NULL; 
  one.ptr = &two; 
  two.ptr = &three; 
  three.ptr = &four; 
  four.ptr = &five; 
  Node* temp = &one; 

    
  // Call function with head of the linked list
  int result = isPalindrome(&one); 
  if(result == 1) 
    cout<<"Linked list is a palindrome\n"; 
  else
    cout<<"Linked list is NOT a palindrome\n"; 
    
} 

import java.util.*; 
  
class linkedList { 
  public static void main(String args[]) 
  { 
    Node one = new Node(1); 
    Node two = new Node(3); 
    Node three = new Node(5); 
    Node four = new Node(3); 
    Node five = new Node(1); 
    one.ptr = two; 
    two.ptr = three; 
    three.ptr = four; 
    four.ptr = five; 
  
    boolean condition = isPalindrome(one); 
    if(condition == true){
      System.out.println("Linked list is a palidrome."); 

    }
    else{
      System.out.println("Linked list is NOT a palidrome."); 

    }
  } 
  static boolean isPalindrome(Node head) 
  { 
    // This pointer will allow the first traversal
    // of the linked list
    Node next = head; 
    
    boolean ispalin = true; 
    Stack<Integer> stack = new Stack<Integer>(); 
    
    // Traverse the linked list and add its elements
    // to the stack
    while (next != null) { 
      stack.push(next.data); 
      next = next.ptr; 
    } 
    // Iterate the linked list again and  
    // check by each element with the stack 
    while (head != null) { 
      int i = stack.pop(); 
      if (head.data == i) { 
        ispalin = true; 
      } 
      else { 
        ispalin = false; 
        break; 
      } 
      // Move to the next element in stack and the list 
      head = head.ptr; 
    } 
    return ispalin; 
  } 
} 
  
class Node { 
  int data; 
  Node ptr; 
  Node(int d) 
  { 
    ptr = null; 
    data = d; 
  } 
} 

Java

class Node: 
  # Constructor to initialize the node object 
  def __init__(self, data): 
    self.data = data 
    self.next = None
  
class LinkedList: 
  # Function to initialize head 
  def __init__(self): 
    self.head = None

  # A utility function to check if the list
  #  is palindrome or not 
  def isPalindrome(self):
    node = self.head
    length = 0
    comp = []
    while node:
      comp.append(node.data)
      node = node.next
      length += 1

    # Traverse the linked list again checking
    # the elements of our stack(comp)
    node = self.head
    for item in comp[::-1]:
      if (item!= node.data):
        return False 
      node = node.next
    return True

# Driver code
llist = LinkedList() 
llist.head = Node('1') 
llist.head.next = Node('3') 
llist.head.next.next = Node("5") 
llist.head.next.next.next = Node("3") 
llist.head.next.next.next.next = Node("1") 
if (llist.isPalindrome()):
  print("Linked List is a palindrome")
else:
  print("Linked List is NOT a palindrome") 


Python

Checking if a linked list is a palindrome

A number is a palindrome if it reads the same forwards as it does backward. For example, the number 123332112333211233321 is a palindrome. Linked lists can also be palindromes if they have the same order of elements when traversed forwards and backward​. 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.  