document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. class Node
  7. {
  8. public:
  9.     int data;
  10.     Node * next;
  11. };
  12.  
  13. class LinkedList
  14. {
  15.     Node *head;
  16. public:
  17.     LinkedList ()
  18.     {
  19.         head = NULL;
  20.     }
  21.    
  22.     LinkedList (Node * head)
  23.     {
  24.         this -> head = head;
  25.     }
  26.    
  27.     Node * newNode (int data)
  28.     {
  29.         Node * node = new Node;
  30.         node -> data = data;
  31.         node -> next = NULL;
  32.         return node;
  33.     }
  34.    
  35.     void insert (int);
  36.     void reverse ();
  37.     bool compare (LinkedList);
  38.     bool isPalindrome ();
  39. };
  40.  
  41. void LinkedList :: insert (int data) // insert at the beginning of the list
  42. {
  43.     Node * node = newNode (data);    
  44.     node -> next = head;
  45.     head = node;
  46. }
  47.  
  48. void LinkedList :: reverse ()
  49. {
  50.     Node *cur, *prev;
  51.     cur = this -> head;
  52.     prev = NULL;
  53.    
  54.     while (cur)
  55.     {
  56.         Node * next = cur -> next;
  57.         cur -> next = prev;
  58.         prev = cur;
  59.         cur = next;
  60.     }
  61.     this -> head = prev;
  62. }
  63.  
  64. bool LinkedList :: compare (LinkedList list)
  65. {
  66.     Node *h1, *h2;
  67.     h1 = this -> head;
  68.     h2 = list.head;
  69.    
  70.     while (h1 && h2)
  71.     {
  72.         if (h1 -> data != h2 -> data)
  73.             return false;
  74.         h1 = h1 -> next;
  75.         h2 = h2 -> next;
  76.     }
  77.    
  78.     if (!h1 && !h2)
  79.         return true;
  80.     return false;
  81. }
  82.  
  83. bool LinkedList :: isPalindrome ()
  84. {
  85.     // If the linked list is empty, then it is a palindrome
  86.    
  87.     if (!(this -> head))
  88.         return true;
  89.    
  90.     LinkedList rev;
  91.     bool comp;
  92.        
  93.     // Get middle of the linked list
  94.    
  95.     Node *slow, *fast, *prev;
  96.     slow = this -> head;
  97.     fast = this -> head;
  98.    
  99.     while (fast -> next && fast -> next -> next)
  100.     {
  101.         prev = slow;
  102.         slow = slow -> next;
  103.         fast = fast -> next -> next;
  104.     }
  105.    
  106.     Node *second_half;
  107.    
  108.     if (fast -> next) // if the length of the linked list is even
  109.     {
  110.         // Set middle of the linked list
  111.        
  112.         second_half = slow -> next;
  113.        
  114.         // Reverse the second half of the list
  115.        
  116.         rev = LinkedList (second_half);
  117.         rev.reverse ();
  118.         slow -> next = NULL;
  119.        
  120.         // Compare reversed second half with the first half
  121.        
  122.         comp = compare (rev);
  123.  
  124.         // Revert the linked list back to original
  125.  
  126.         rev = LinkedList (second_half);
  127.         rev.reverse ();
  128.         slow -> next = second_half;
  129.     }
  130.     else // if the length of the linked list is odd
  131.     {
  132.         // Set middle of the linked list
  133.        
  134.         second_half = slow -> next;
  135.         prev -> next = NULL;
  136.        
  137.         // Reverse the second half of the list
  138.        
  139.         rev = LinkedList (second_half);
  140.        
  141.         // Compare reversed second half with the first half
  142.        
  143.         comp = compare (rev);
  144.        
  145.         // Revert the linked list back to original
  146.        
  147.         rev = LinkedList (second_half);
  148.         prev -> next = slow;
  149.         slow -> next = second_half;
  150.     }
  151.    
  152.     return comp;
  153. }
  154.  
  155. int main (void)
  156. {
  157.     LinkedList list = LinkedList ();
  158.     list.insert (1);
  159.     list.insert (2);
  160.     list.insert (3);
  161.     list.insert (3);
  162.     list.insert (1);
  163.    
  164.     if (list.isPalindrome ())
  165.         printf ("Is palindrome.\\n");
  166.     else
  167.         printf ("Is not palindrome.\\n");
  168.    
  169.     return 0;
  170. }
');