#include <iostream>
#include <cstdio>
using namespace std;
class Node
{
public:
int data;
Node * next;
};
class LinkedList
{
Node *head;
public:
LinkedList ()
{
head = NULL;
}
LinkedList (Node * head)
{
this -> head = head;
}
Node * newNode (int data)
{
Node * node = new Node;
node -> data = data;
node -> next = NULL;
return node;
}
void insert (int);
void reverse ();
bool compare (LinkedList);
bool isPalindrome ();
};
void LinkedList :: insert (int data) // insert at the beginning of the list
{
Node * node = newNode (data);
node -> next = head;
head = node;
}
void LinkedList :: reverse ()
{
Node *cur, *prev;
cur = this -> head;
prev = NULL;
while (cur)
{
Node * next = cur -> next;
cur -> next = prev;
prev = cur;
cur = next;
}
this -> head = prev;
}
bool LinkedList :: compare (LinkedList list)
{
Node *h1, *h2;
h1 = this -> head;
h2 = list.head;
while (h1 && h2)
{
if (h1 -> data != h2 -> data)
return false;
h1 = h1 -> next;
h2 = h2 -> next;
}
if (!h1 && !h2)
return true;
return false;
}
bool LinkedList :: isPalindrome ()
{
// If the linked list is empty, then it is a palindrome
if (!(this -> head))
return true;
LinkedList rev;
bool comp;
// Get middle of the linked list
Node *slow, *fast, *prev;
slow = this -> head;
fast = this -> head;
while (fast -> next && fast -> next -> next)
{
prev = slow;
slow = slow -> next;
fast = fast -> next -> next;
}
Node *second_half;
if (fast -> next) // if the length of the linked list is even
{
// Set middle of the linked list
second_half = slow -> next;
// Reverse the second half of the list
rev = LinkedList (second_half);
rev.reverse ();
slow -> next = NULL;
// Compare reversed second half with the first half
comp = compare (rev);
// Revert the linked list back to original
rev = LinkedList (second_half);
rev.reverse ();
slow -> next = second_half;
}
else // if the length of the linked list is odd
{
// Set middle of the linked list
second_half = slow -> next;
prev -> next = NULL;
// Reverse the second half of the list
rev = LinkedList (second_half);
// Compare reversed second half with the first half
comp = compare (rev);
// Revert the linked list back to original
rev = LinkedList (second_half);
prev -> next = slow;
slow -> next = second_half;
}
return comp;
}
int main (void)
{
LinkedList list = LinkedList ();
list.insert (1);
list.insert (2);
list.insert (3);
list.insert (3);
list.insert (1);
if (list.isPalindrome ())
printf ("Is palindrome.\\n");
else
printf ("Is not palindrome.\\n");
return 0;
}