C++ program to check if a singly linked list is palindrome.

Today we are going to see if a singly linked list is a palindrome or not in C++. A palindrome number is a number that looks the same in both backward and forwards. Examples are 1001 and 121. Now we will do this for the node’s data of a linked list. We will create a function which returns 1 if the list is palindrome and 0 if it isn’t. Then we will pass the head pointer of that list as the parameter for that function.

We will use a vector for storing the digits of the linked list. Next, we will check if an element is equal to its corresponding element at the end of the vector. We have to do this for all the elements of 1st half of the vector. If for some element this is not true, then the linked list is not a palindrome. Now, let’s see how to implement this using C++.

Check if a singly linked list is palindrome or not in C++

First, we will enter the number of nodes for our linked list. Then, we enter the data for it. Next, we call our check function, which returns 1 for palindrome and 0 for not palindrome. Let’s look at the program.

#include<bits/stdc++.h>
using namespace std;

struct Node{
  int data;
  struct Node *next;
  Node(int x){
    data=x;
    next=NULL;
  }
};

void append(struct Node** head_ref,struct Node** tail_ref,int new_data)
{
  struct Node* new_node =new Node(new_data);
  if(*head_ref==NULL)
    *head_ref=new_node;
  else
    (*tail_ref)->next=new_node;
  *tail_ref=new_node;
}

bool isPalindrome(Node *head);

int main()
{
  int i,n,l;
  struct Node *head=NULL, *tail=NULL;
  cin>>n;
  for(i=1;i<=n;i++)
  {
    cin>>l;
    append(&head,&tail,l);
  }
  cout<<isPalindrome(head)<<endl;

  return 0;
}

bool isPalindrome(Node *head)
{
    bool ans=true;
    vector<int> v;
    while(head!=NULL)
    {
        int temp=head->data;
        v.push_back(temp);
        head=head->next;
    }
    int h=0;
    int n=v.size();
    for(int i=0;i<v.size()/2;i++)
    {
        if(v[i]==v[n-i-1])
        {
            continue;
        }
        else
        {
            ans=false;
            break;
        }
    }
    return ans;
}

You can see that the function ‘isPalindrome’ takes the head pointer as a parameter, which stores the address of the head node of the linked list. Now, let’s look at some test cases.

Test case 1:-

3
1 2 1
1

Test case 2:-

4
1 2 3 4
0

In the first test case, the output is 1, which indicates that the linked list is a palindrome. But in the second test case, it isn’t. So the output is 0.

I hope you found this article useful. For further practice, try to implement this for doubly-linked lists. It will enhance your grasp of the topic.

Also read: Palindrome check for number or string in C++

Leave a Reply

Your email address will not be published. Required fields are marked *