Related Tags

palindrome
list

# 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 $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.
Traverse the linked list, pushing elements in a stack at each step.
1 of 9

## 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;
};

// This pointer will allow the first traversal
// Declare a stack
stack <int> s;

// 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
int i=s.top();

return false;
}
// Move to the next element in stack and the list
s.pop();
}

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;

int result = isPalindrome(&one);
if(result == 1)
else
cout<<"Linked list is NOT a palindrome\n";

} 

RELATED TAGS

palindrome