Check if a linked list is a palindrome in C++
By Sakshi GuptaIn this tutorial, we will learn how to check if a linked list is a palindrome in C++. A palindrome is a word, phrase or a sequence that reads the same backward and forwards.
For example-
121 is a palindrome.
123321 is a palindrome.
1234554321 is a palindrome.
12345421 is not a palindrome.
112233112233 is not a palindrome again.
C++ program to check if a linked list is a palindrome
Method 1:
We will be using STL(Standard template library) in this method.
- In the first pass, compare the first and the last element.
- In the second pass, compare the second and the second last element.
- Do this for n/2 times i.e till we reach the middle of the list.
- Keep a flag variable. If anywhere, the elements are not equal set the flag to 0 and break from the loop.
The last element is accessed by:
list<int>::iterator tail=mylist.end();
But since it refers to this position shown in the figure, we have to decrement it by 1 to reach the last element of the linked list.
Here is the C++ code:
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> mylist;
int n=9;
int data;
for(int i=0;i<n;i++)
{
cin>>data;
mylist.push_front(data);
}
list<int>::iterator head=mylist.begin();
list<int>::iterator tail=mylist.end();
--tail;//To locate the element at last iterator
bool flag=1;
for(int i=0;i<n/2;i++)
{
if(*head==*tail)
{
head++;
tail--;
}
else
{
flag=0;
break;
}
}
flag ? cout<<"yes it's a palindrome" : cout<<"no,it's not a palindrome";
}
INPUT: 1 2 3 3 2 1
OUTPUT:
yes it's a palindrome
INPUT: 1 2 3 4 5 3 2 1
OUTPUT:
no, it's not a palindrome
Method 2:
We will be using STL again in this method.
- First, we will reach to the middle of the linked list. This we will do by incrementing the head2 iterator by n/2 times if n is even and n/2+1 times if n is odd.
- Then we will create another list of second-half elements and reverse it.
- Now, compare the elements of the first half of the original list and the second list.
- If they are all equal, it’s a palindrome.
Here, is the code:
#include <bits/stdc++.h>
using namespace std;
int main() {
list<int> mylist;
int n=9;
int data;
for(int i=0;i<n;i++)
{
cin>>data;
mylist.push_back(data);
}
list<int>::iterator head=mylist.begin();
list<int>::iterator head2=mylist.begin();
int j=0;
if(n%2==0)//if number of elemnts are even
{
j=n/2;
}
else
{
j=(n/2)+1;
}
//incrementing head2 till it reaches the middle of the list
for(int i=0;i<j;i++)
{
head2++;
}
//creating another list of second half elements of first list
list<int> l2;
for(int i=0;i<n/2;i++)
{
l2.push_back(*head2);
head2++;
}
//reversing the second list
l2.reverse();
int flag=1;
head2=l2.begin();
//comparing elements of first and second list
for(int i=0;i<n/2;i++)
{
if(*head2==*head)
{
head2++;
head++;
}
else
{
flag=0;
break;
}
}
flag ? cout<<"yes it's a palindrome" : cout<<"no,it's not a palindrome";
}
INPUT: 1 2 3 3 2 1
OUTPUT:
yes it's a palindrome
Also, refer to:
Thank you!
Leave a Reply