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

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

   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

Your email address will not be published.