linkedlistpalindrome.txt

#include <bits/stdc++.h> 
/****************************************************************

    Following is the class structure of the LinkedListNode class:

    template <typename T>
    class LinkedListNode
    {
    public:
        T data;
        LinkedListNode<T> *next;
        LinkedListNode(T data)
        {
            this->data = data;
            this->next = NULL;
        }
    };

*****************************************************************/

bool isPalindrome(LinkedListNode<int> *head) {
    // Write your code here.
    if(!head || !head->next){return true;}
    LinkedListNode<int> *temp2=new LinkedListNode<int>(1);
    LinkedListNode<int> *slow=temp2;
    LinkedListNode<int> *fast=temp2;
    temp2->next=head;
    while(fast && fast->next){
        fast=fast->next->next;
        slow=slow->next;
    }
    LinkedListNode<int> *temp=slow;
//     slow=slow->next;
    LinkedListNode<int> *mid=slow->next;;
//     //reverse the list now
    LinkedListNode<int> *next;
//     cout<<slow->data<<endl;
//     cout<<temp->data<<endl<<slow->data<<endl<<next->data<<endl;
    while(mid){
        next=mid->next;
        mid->next=temp;
        temp=mid;
        mid=next;
    }
    slow->next->next=NULL;
    slow->next=NULL;
    LinkedListNode<int> *end=temp;
//     cout<<head->data<<" "<<end->data<<endl;
//     cout<<head->next->data<<" "<<end->next->data<<endl;
//     cout<<head->next->next->data<<" "<<end->next->next->data<<endl;
//     cout<<head->next->next->next->data<<" "<<end->next->next->next->data<<endl;
//     cout<<head->next->next->next->next->data<<" "<end->next->next->next->next->data<<endl;
    while(head && end){
        if(head->data!=end->data){return false;}
        head=head->next;
        end=end->next;
    }
    return true;


}