Write a program to check whether a linked list is palindromic linked list O(n) complexity. Do not use extra space.

/*

1.Find out the middle of the linked list, the middle can be found out by using two pointers slow and fast, slow is incremented by 1 and the fast by 2, when the fast reaches the end the slow will be at the middle.

The fast pointer stops when either fast next is NULL or the next of next is NULL. When the next is NULL then the list is odd and when the next of next is NULL the list os even numbered. 

2. Assign middleNode pointer to slow pointer.

  for odd linked list assign secondHalf pointer to middleNode->next

  for even linked list assign secondHalf pointer to middleNode->next->next

3. Now recurse on linked list until middleNode is reached.

4. After firstHalf pointer reaches middleNode pointer(base case) we compare secondHalf and firstHalf. 

Three important function

getMiddleNode()

recursivePalindromeCheck()

checkPalindrome()

check

*/

#include<iostream.h>

#include<conio.h>

class node

{

public:

       int data;

       node *next;

       node()

       {

             next = NULL;

             data = 0;

       }

};

class linkedList

{

public:

    node *start;

    node *middleNode;

    node *secondHalf;

    bool isPalindrome;

    linkedList()

    {

        start = NULL;

        middleNode = NULL;

        secondHalf = NULL;

        isPalindrome = true;

    }

    

    void insertInFront(int val)

    {

         node *newNode = new node;

         newNode->data = val;

         if(start == NULL)

         {

                  start=newNode;

         }

         else

         {

             newNode->next = start;

             start = newNode;

         }

    }

    

    void display()

    {

         node *ptr = start;

         while(ptr != NULL)

         {

                   cout<<ptr->data<<" -> ";

                   ptr = ptr->next;

         }

    }

    

    void getMiddleNode()

    {

      node *slow = start,*fast = start->next;

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

      {

                       fast = fast->next->next;

                       slow = slow->next;

      }

      if(fast->next == NULL)

                    secondHalf = slow->next;

      else

                    secondHalf = slow->next->next;

      middleNode = slow;

    }

          

    

    bool checkPalindrome()

    {

      getMiddleNode();

      cout<<"\nmiddleNode = "<<middleNode->data<<"\n";

      cout<<"\nSecondHalfNode = "<<secondHalf->data<<"\n";

      getch();

      recursivePalindromeCheck(start);

      if(isPalindrome)

                       cout<<"PALINDROMIC LINKED LIST";

      else

          cout<<"NON PALINDROMIC LINKED LIST";

      

    }

    

    void recursivePalindromeCheck(node *firstHalf)

    {

      if( firstHalf == middleNode )

          ;

      else

      {

          recursivePalindromeCheck(firstHalf->next);

          

      }

      if( firstHalf->data == secondHalf->data)

              secondHalf = secondHalf->next;

          else

              isPalindrome = false;

    }

};

int main()

{

    linkedList list;

    int choice,val;

    while(1)

    {

        system("CLS");

        cout<<"1. Insert in Front\n2. Display\n3. Ispalindrome?\n4. Exit\n\nchoice? ";

        cin>>choice;

        switch(choice)

        {

            case 1:

                 cout<<"\nEnter Value : ";

                 cin>>val;

                 list.insertInFront(val);

                 break;

            case 2:

                 list.display();

                 getch();

                 break;

            case 3:

                 list.checkPalindrome();

                 getch();

                 break;

            case 4:

                 exit(0);

            defaule:

                    cout<<"Invalid Input";

        }

    }

}