Check if a linked list is a palindrome in C++
In 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