Check whether the Linked List is a Palindrome or not

Algorithm:

The following method takes O(n) time and O(1) extra space.

1) Get the middle of the linked list.

2) Reverse the second half of the linked list.

3) Check if the first half and second half are identical.

4) Construct the original linked list by reversing the second half again and attaching it back to the first half

Solution:

/*

Problem description

to check whether the given list is

a palindrome or not

submitted by

Arjun Mishra

*/

#include<iostream>

#include<stdlib.h>

using namespace std;

//node structure

struct node

{

       char data;

       node *next;

}*head,*tail,*temp;

//function to push a node into the linked list

void push(char val)

{

     temp=(struct node*)malloc(sizeof(struct node));

     if(!(temp))

     {

      cout<<"memory not available\n";

      return;

     }

     temp->data=val;

     temp->next=NULL;

     //if the node is the very first node

     if(head==NULL)

     {

      head=temp;

      tail=temp;

     }

     else//for other subsequent nodes

     {

      tail->next=temp;

      tail=temp;

     }

}

bool reverseAndCheck(struct node *head,struct node* joint)

{

     if(head==NULL)

     {

                   cout<<"List is Empty!Cannot reverse\n";

                   return true;

     }

     if(head->next==NULL)

     {

                   return true;      

     }

     while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      //checking whether the it is a palindrome or not

      struct node* iterator1,*iterator2;

      iterator1=::head;

      iterator2=head;

      while(iterator1!=NULL&&iterator2!=NULL)

      {

       if(iterator1->data!=iterator2->data)

       {

       //first rearranging the list and then returning false

       while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      joint->next=head;

       return false;

       }

       iterator1=iterator1->next;

       iterator2=iterator2->next;

      }

      //first rearranging the list and then returning true

        while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      joint->next=head;

      return true;

}

struct node* findMidPointer()

{

     temp=head;

     node *temp1;

     temp1=head;

     while(temp!=NULL&&temp->next!=NULL)

     {

     temp1=temp1->next;

     temp=temp->next;

     temp=temp->next;

     }

     return temp1;  

}

bool isPalin()

{

     /*

     logic:

     traversing till half...reversing the other half...

     further matching it with the first half

     time-complexity=O(n)

     space-complexity=O(1)

     */

     node *mid,*temp2;

     temp2=findMidPointer();

     mid=temp2->next;

     temp2->next=NULL;

     if(reverseAndCheck(mid,temp2))

     return true;

     else

     return false;

}

void finaltraverse()

{

     if(head==NULL)

     {

                   cout<<"List is empty!\n";

                   return;

     }

     temp=head;

     while(temp!=NULL)

     {

                      cout<<temp->data<<"->";

                      temp=temp->next;

     }

     cout<<"NULL"<<endl;

}

int main()

{

    //let the string be MALAYALAM

    push('M');

    push('A');

    push('L');

    push('A');

    push('Y');

    push('A');

    push('L');

    push('A');

    push('M');

    //checking whether,it's palindrome or not

    if(isPalin())

    {

     cout<<"Yes!it is a palindrome\n";

    }

    else

    {

     cout<<"No!it is not a palindrome\n";

    }

    cout<<"the original list is\n";

    finaltraverse();

    getchar();

    return 0;

}