# Check palindrome in given Linked List

There are many ways to check given linked list elements are contains palindrome. We can solve this problem by using of Stack and Recursion are very easily. In this post mentioning both ways to solve this problem solution.

Method 1: This is a simplest solution of this problem. create a empty stack and first insert all elements of linked list into an stack. After that comparing the stack top (root) element is equal to linked list node. when it is equals then remove stack top element.

Similar way compare stack top elements to linked list upcoming nodes. If stack and current linked list nodes are not same then in this case linked list are not contain palindrome. Otherwise exist.

Note : Using stack, In this case you'll can create two type of stack. First are creating a new structure(class) which are contains two fields (element pointer and next node pointer).

``````struct Stack{
Node*element;
Stack*next;
};``````

Here element is an Linked list node pointer. But we are already create a structure for linked list node which are contain two fields (data and next pointer). So we can create a new Structure or we can use existing structure. In given below program are using existing structure of linked list node.

``````//C Program
//Check palindrome in given linked list
//Using Stack
#include<stdio.h>
#include <stdlib.h> //for malloc function

//create structure
struct Node{
int data;
struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
node->next=NULL;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
//add node at last possition
temp->next=node;
}
}
}
void push(struct Node**root,int value){
//Create dynamic a new node to add stack element
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
node->next=*root;
*root=node;
}
}
int pop(struct Node**root){
int data = (*root)->data;
(*root)= (*root)->next;
return data;
}
//Display element of Node
void display(struct Node*temp){

if(temp==NULL){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
//Check the palindrome in given linked list
}else{

//Add Element into a new stack
while(temp!=NULL){
//Add element to stack
push(&stack,temp->data);
temp=temp->next;
}

//Compare stack and linked list element
while(temp!=NULL){

if(temp->data!=pop(&stack)){

break;
}
temp=temp->next;
}

if(stack!=NULL){
printf("\nNo\n");
//Remove existing element of stack
while(stack!=NULL){
pop(&stack);
}
}else{
printf("\nYes\n");
}
}
}
int main(){
//create node pointer
//insert element of linked list

//display all node

//display all node
return 0;

}``````

#### Output

``````1  2  3  2  1
Yes
1  2  3  2  1  2
No``````
``````//C++ Program
//Check palindrome in given linked list
//using stack
#include<iostream>
using namespace std;

//create structure
struct Node{
int data;
struct Node*next;
};
public:
void insert(int);
void display();
void push(Node**,int );
int pop(Node**);
void palindrome();
};
}
//insert node at end of linked list
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
//base condition
}else{
while(temp->next!=NULL){
temp=temp->next;
}
//add newly node at last
temp->next=node;
}
}
}
//display all node value in linked list
}
else{
cout<<"Linked List : ";
while(temp!=NULL){
//print node value
cout<<temp->data<<" ";
temp=temp->next;
}
}
}
//Add element into an stack
void LinkedList:: push(struct Node**root,int value){
//Create dynamic a new node
Node*node=new Node;
if(node==NULL){
cout<<("Memory overflow\n");
}else{
node->data=value;
node->next=*root;
*root=node;
}
}
int data = (*root)->data;
(*root)= (*root)->next;
return data;
}
//Check the palindrome in given linked list
}else{

//Add Element into a new stack
while(temp!=NULL){
//Add element to stack
push(&stack,temp->data);
temp=temp->next;
}

//Compare stack and linked list element
while(temp!=NULL){

if(temp->data!=pop(&stack)){

break;
}
temp=temp->next;
}

if(stack!=NULL){
cout<<("\nNo\n");
//Remove existing element of stack
while(stack!=NULL){
pop(&stack);
}
}else{
cout<<"\nYes\n";
}
}
}
int main(){

//create object
//insert element of linked list
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

//display all node
obj.display();
obj.palindrome();

obj.insert(2);

obj.display();
obj.palindrome();

return 0;
}``````

#### Output

``````Linked List : 1 2 3 2 1
Yes
Linked List : 1 2 3 2 1 2
No
``````
``````//Java Program
//Check palindrome in given linked list
//Using stack
class Node {
public int data;
public Node next;
public Node(int value) {
data = value;
next = null;
}
}
public class LinkedList {

public Node root; //stack node

//Class conors
root = null;
}
//insert element
public void insert(int value) {
//Create  node
Node node = new Node(value);

if (head == null) {
} else {
Node temp = head;
//find last node
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}

}
//Display all Linked List elements
public void display() {
if (head != null) {
System.out.print("Linked List Element :");
Node temp = head;
while (temp != null) {
System.out.print("  " + temp.data);
temp = temp.next;
}
} else {
}
}

public void push(int value) {
//Create dynamic a new node
Node node = new Node(value);
if (node == null) {
System.out.println("Memory overflow\n");
} else {
node.data = value;
node.next = root;
}
root = node;
}
//Remove stack element
int pop() {
int data = root.data;
root = root.next;
return data;
}
//Check the palindrome in given linked list
void palindrome() {
if (head == null) {
} else {
Node temp = head;
root = null;
//Add Element into a new stack
while (temp != null) {
//Add element to stack
push(temp.data);
temp = temp.next;
}

//Compare stack and linked list element
while (temp != null) {

if (temp.data != pop()) {

break;
}
temp = temp.next;
}

if (root != null) {
System.out.println("\nNo");
//Remove existing element of stack
while (root != null) {
pop();
}
} else {
System.out.println("\nYes");
}
}
}
public static void main(String[] args) {

obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

obj.display();
obj.palindrome();

obj.insert(2);

obj.display();
obj.palindrome();
}
}``````

#### Output

``````Linked List Element :  1  2  3  2  1
Yes
Linked List Element :  1  2  3  2  1  2
No``````
``````#Python Program
#Check palindrome in given linked list
#using Stack
class Node:
def __init__(self,data):
self.data=data
self.next=None

def __init__(self):
#Assign default value
self.root=None

#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=node

def display(self):
return

while(temp!=None):
print(temp.data,end=" ")
temp=temp.next

def push(self,value):
#Create dynamic a new node
node=Node(value);
if(node==None):
print("Memory overflow\n");
else:
node.next=self.root;

self.root=node;

#Remove stack element
def pop(self):
data = self.root.data;
self.root = self.root.next;
return data;

#Check the palindrome in given linked list
def palindrome(self):
else:
self.root=None;
#Add Element into a new stack
while(temp!=None):
#Add element to stack
self.push(temp.data);
temp = temp.next;

#Compare stack and linked list element
while(temp!=None):

if(temp.data!=self.pop()):
break;

temp=temp.next;

if(self.root!=None):
print("\nNo");
#Remove existing element of stack
while(self.root!=None):
self.pop();
else:
print("\nYes");

def main():
#Create Object of class Linked
obj.insert(1)
obj.insert(2)
obj.insert(3)
obj.insert(2)
obj.insert(1)
obj.display()
obj.palindrome();

obj.insert(2)
obj.display()
obj.palindrome();

if __name__=="__main__":
main()``````

#### Output

``````1 2 3 2 1
Yes
1 2 3 2 1 2
No
``````
``````//C# Program
//Check palindrome in given linked list
//Using Stack

using System;
//node class
public class Node{
public  int data;
public  Node next;
}
{
root = null;
}
//insert node of linked list
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get last node
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
}
//display linked list nodes value
public void display(){
Console.Write("Empty List");
}else{
while(temp!=null){
Console.Write("{0} ",temp.data);
temp=temp.next;
}

}
}

public void push(int value){
//Create dynamic a new node
Node node=new Node();
if(node==null){
Console.WriteLine("Memory overflow\n");
}else{
node.data=value;
node.next=root;
}
root=node;
}
//Remove stack element
public int pop(){
int data = root.data;
root = root.next;
return data;
}
//Check the palindrome in given linked list
public void palindrome(){
}else{
root=null;
//Add Element into a new stack
while(temp!=null){
//Add element to stack
push(temp.data);
temp = temp.next;
}

//Compare stack and linked list element
while(temp!=null){

if(temp.data!=pop()){

break;
}
temp=temp.next;
}

if(root!=null){
Console.WriteLine("\nNo");
//Remove existing element of stack
while(root!=null){
pop();
}
}else{
Console.WriteLine("\nYes");
}
}
}
static void Main()
{
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

obj.display();
obj.palindrome();

obj.insert(2);

obj.display();
obj.palindrome();
}
}``````

#### Output

``````1 2 3 2 1
Yes
1 2 3 2 1 2
No``````
``````<?php
//Php program
//Check palindrome in given linked list
//Using Stack
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}

function __construct()
{
\$root=NULL;
}
/*
Append the Given data value at end of linked list
Fun : insert
Parm: data value
@return None
*/
public function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//find last node of linked list
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
//add new node to last of linked list
\$temp->next=\$newNode;
}
}
//Display all inserted node in linked list
public function display()
{
{
echo "Empty Linked List";
}
else{
echo "Linked List :";
while(\$temp!=NULL){
//display node value
echo "  ".\$temp->data;
\$temp=\$temp->next; //visit to next node
}
}
}
function push(\$value)
{
//Create dynamic a new node
\$node=new Node(\$value);
if(\$node==NULL)
{
echo ("Memory overflow<br>");
}else
{
\$node->next=\$this->root;
\$this->root=\$node;
}
}
public function pop()
{
\$data = \$this->root->data;
\$this->root= \$this->root->next;
return \$data;
}

//Check the palindrome in given linked list
public function palindrome()
{
{
echo ("Empty linked list");
}
else
{
\$this->root=NULL;

//Add Element into a new stack
while(\$temp!=NULL)
{
//Add element to stack
\$this->push(\$temp->data);
\$temp=\$temp->next;
}

//Compare stack and linked list element
while(\$temp!=NULL)
{

if(\$temp->data!=\$this->pop())
{

break;
}
\$temp=\$temp->next;
}

if(\$this->root!=NULL)
{
echo ("<br>No<br>");
//Remove existing element of stack
while(\$this->root!=NULL)
{
\$this->pop();
}
}else
{
echo ("<br>Yes<br>");
}
}
}
}
function main(){
//Make a object of LinkedList class

/*
Insert following nodes in linked list
*/
\$obj->insert(1);
\$obj->insert(2);
\$obj->insert(3);
\$obj->insert(2);
\$obj->insert(1);

\$obj->display();
\$obj->palindrome();

\$obj->insert(2);
\$obj->display();
\$obj->palindrome();

}
main();
?>``````

#### Output

``````Linked List : 1 2 3 2 1
Yes
Linked List : 1 2 3 2 1 2
No``````

Method 2 Recursion is an another way to find palindrome in given linked list. Here given code implementation process.

``````//C Program
//Check palindrome in given linked list
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure
struct Node{
int data;
struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
//insert Node element
void insert(struct Node**head,int value){
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
node->next=NULL;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
//add node at last possition
temp->next=node;
}
}
}
//Display element of Node
void display(struct Node*temp){

if(temp==NULL){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
//Check the palindrome using linked list
void palindrome(struct Node*front,struct Node**back,int *status){

if(*status==1 && front!=NULL && *back!=NULL){

palindrome(front->next,back,status);

if(front->data!=(*back)->data){
*status=0;
}else{
*back=(*back)->next;
}
}
}

int status=1;

if(status==1){
printf("\nYes\n");
}else{
printf("\nNo\n");
}
}else{
}
}
int main(){
//create node pointer
//insert element of linked list

//display all node

return 0;
}``````

#### Output

``````1  2  3  2  1
Yes
1  2  3  2  1  2
No``````
``````//C++ Program
//Check palindrome in given linked list
#include<iostream>
using namespace std;

//create structure
struct Node{
int data;
struct Node*next;
};
public:
void insert(int);
void display();
void test_palindrome();
void palindrome(Node*,Node**,int *);
};
}
//insert node at end of linked list
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
//base condition
}else{
while(temp->next!=NULL){
temp=temp->next;
}
//add newly node at last
temp->next=node;
}
}
}
//display all node value in linked list
}
else{
cout<<"Linked List : ";
while(temp!=NULL){
//print node value
cout<<temp->data<<" ";
temp=temp->next;
}
}

}
//Check the palindrome using linked list
void LinkedList:: palindrome(Node*front,Node**back,int *status){

if(*status==1 && front!=NULL && *back!=NULL){

palindrome(front->next,back,status);

if(front->data!=(*back)->data){
*status=0;
}else{
*back=(*back)->next;
}
}
}
//This function are managing to display status of palindrome

int status=1;

if(status==1){
cout<<("\nYes")<<endl;
}else{
cout<<("\nNo")<<endl;
}
}else{
}
}
int main(){

//create object
//insert element of linked list
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

//display all node
obj.display();
obj.test_palindrome();

obj.insert(2);

obj.display();
obj.test_palindrome();
return 0;
}``````

#### Output

``````Linked List : 1 2 3 2 1
Yes
Linked List : 1 2 3 2 1 2
No
``````
``````//Java Program
//Check palindrome in given linked list
class Node {
public int data;
public Node next;
public Node(int value) {
data = value;
next = null;
}
}
public class LinkedList {

public Node back;
public int status;
//Class conors
back = null;
status = 1;
}
//insert element
public void insert(int value) {
//Create  node
Node node = new Node(value);

if (head == null) {
} else {
Node temp = head;
//find last node
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}

}
//Display all Linked List elements
public void display() {
if (head != null) {
System.out.print("Linked List Element :");
Node temp = head;
while (temp != null) {
System.out.print("  " + temp.data);
temp = temp.next;
}
} else {
}
}
//Check the palindrome using linked list
public void palindrome(Node front) {

if (status == 1 && front != null && back != null) {

palindrome(front.next);

if (front.data != back.data) {
status = 0;
} else {
back = back.next;
}
}
}
//This function are managing to display status of palindrome
public void testPalindrome() {
status = 1;
if (head != null) {
if (status == 1) {
System.out.println("\nYes");
} else {
System.out.println("\nNo");
}
} else {
}
}
public static void main(String[] args) {

obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

obj.display();
obj.testPalindrome();

obj.insert(2);

obj.display();
obj.testPalindrome();
}
}``````

#### Output

``````Linked List Element :  1  2  3  2  1
Yes
Linked List Element :  1  2  3  2  1  2
No``````
``````#Python Program
#Check palindrome in given linked list
class Node:
def __init__(self,data):
self.data=data
self.next=None

def __init__(self):
#Assign default value

#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=node

def display(self):
return

while(temp!=None):
print(temp.data,end=" ")
temp=temp.next

#Check the palindrome using linked list
def palindrome(self, front):

if( self.status==1 and front!=None and  self.back!=None):

self.palindrome(front.next)

if(front.data!=self.back.data):
self.status=0
else:
self.back=self.back.next

#This function are managing to display status of palindrome
def testPalindrome(self):
self.status=1
if(self.status==1):
print("\nYes")
else:
print("\nNo")
else:

def main():
#Create Object of class Linked
obj.insert(1)
obj.insert(2)
obj.insert(3)
obj.insert(2)
obj.insert(1)
obj.display()
obj.testPalindrome();

obj.insert(2)
obj.display()
obj.testPalindrome();

if __name__=="__main__":
main()``````

#### Output

``````1 2 3 2 1
Yes
1 2 3 2 1 2
No
``````
``````//C# Program
//Check palindrome in given linked list
using System;
//node class
public class Node{
public  int data;
public  Node next;
}
{
}
//insert node of linked list
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get last node
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
}
//display linked list nodes value
public void display(){
Console.Write("Empty List");
}else{
while(temp!=null){
Console.Write("{0} ",temp.data);
temp=temp.next;
}

}
}
//Check the palindrome using linked list
public void palindrom(Node front,ref Node back,ref int status){

if( status==1 && front!=null &&  back!=null){

palindrom(front.next,ref back,ref status);

if(front.data!=back.data){
status=0;
}else{
back=back.next;
}
}
}
//This function are managing to display status of palindrome
public void test_palindrom(){

int status=1;

if(status==1){
Console.WriteLine("\nYes");
}else{
Console.WriteLine("\nNo");
}
}else{
}
}
static void Main()
{
obj.insert(1);
obj.insert(2);
obj.insert(3);
obj.insert(2);
obj.insert(1);

obj.display();
obj.test_palindrom();

obj.insert(2);

obj.display();
obj.test_palindrom();
}
}``````

#### Output

``````1 2 3 2 1
Yes
1 2 3 2 1 2
No
``````
``````<?php
//Php program
//Check palindrome in given linked list
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}

function __construct()
{
}
/*
Append the Given data value at end of linked list
Fun : insert
Parm: data value
@return None
*/
public function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//find last node of linked list
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
//add new node to last of linked list
\$temp->next=\$newNode;
}
}
//Display all inserted node in linked list
public function display()
{
{
echo "Empty Linked List";
}
else{
echo "Linked List :";
while(\$temp!=NULL){
//display node value
echo "  ".\$temp->data;
\$temp=\$temp->next; //visit to next node
}
}
}
//Check the palindrome using linked list
public function palindrom(\$front,&\$back,&\$status){

if(\$status==1 && \$front!=NULL && \$back!=NULL){

\$this->palindrom(\$front->next,\$back,\$status);

if(\$front->data!=\$back->data){
\$status=0;
}else{
\$back=\$back->next;
}
}
}
public function test_palindrom(){

\$status=1;

if(\$status==1){
echo "<br> Yes <br>";
}else{
echo "<br> No <br>";
}
}else{
echo ("<br>Empty linked list");
}
}
}
function main(){
//Make a object of LinkedList class

/*
Insert following nodes in linked list
*/
\$obj->insert(1);
\$obj->insert(2);
\$obj->insert(3);
\$obj->insert(2);
\$obj->insert(1);

\$obj->display();
\$obj->test_palindrom();

\$obj->insert(2);
\$obj->display();
\$obj->test_palindrom();

}
main();
?>``````

#### Output

``````Linked List : 1 2 3 2 1
Yes
Linked List : 1 2 3 2 1 2
No ``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.