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.

1. In the first pass, compare the first and the last element.
2. In the second pass, compare the second and the second last element.
3. Do this for n/2 times i.e till we reach the middle of the list.
4. 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 tail=mylist.end();

--tail;//To locate the element at last iterator
bool flag=1;

for(int i=0;i<n/2;i++)
{

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

1. 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.
2. Then we will create another list of second-half elements and reverse it.
3. Now, compare the elements of the first half of the original list and the second list.
4. 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);
}

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++)
{
}
//creating another list of second half elements of first list
list<int> l2;

for(int i=0;i<n/2;i++)
{
}
//reversing the second list
l2.reverse();
int flag=1;

//comparing elements of first and second list
for(int i=0;i<n/2;i++)
{
{
}
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!