Palindrome Linked List (LeetCode)

 Algorithms and approach and Intuitions

approach 1:

1.tranverse the linkedlist and put the elem of linkedlist in empty vector , string , arr 

2.if string then reverse the string and put the reversed string in a another string name P 

3.compare them if true return true if not then return false use the ternary operator in c++;

4.bool ans = if(s==p)?return true:return fasle;

time complexity is O(2N) and space complexity is O(N);

approach 2:

step1:find the middle of linkedList using tortoise-hare appraoch

make two ptr slow and fast 

move the slow by 1 and fast by 2 until the fast->next(odd) and fast->next->next(even) 

step2:reverse the linkelist using 

return the prev to slow->next 

step3: move the head and slow=slow->next by 1 until the slow==NULL 

then if not equal return false if equal then 

get outside of while  loop then write return false;

Code 

 ListNode* reverseList(ListNode* head){

        //reverse the linkedlist 

        ListNode* prev = NULL;

        ListNode* next = NULL;

        // O(n/2)

        while(head!=NULL){

            next = head->next;

            head->next = prev;

            prev = head;

            head = next;

        }

        return prev;

    }

    bool isPalindrome(ListNode* head) {

        //naive approach 

        // string s = "";

        // ListNode* temp = head;

        // while(temp!=NULL){

        //     s+=to_string(temp->val);

        //     temp = temp->next;

        // }

        // string a = s;

        // reverse(a.begin(),a.end());

        // if(a==s){

        //     return true;

        // }

        // return false;

        if(head==NULL || head->next==NULL){

            return true;

        }

        //middle of linkedlist 

        ListNode* slow = head;

        ListNode* fast = head;

        // O(n/2)

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

            slow=slow->next;

            fast=fast->next->next;

        }

        slow->next = reverseList(slow->next);

        //check palindrome 

        // ListNode* temp = head;

        slow=slow->next;

        // O(n/2)

        while(slow!=NULL){

            if(slow->val != head->val){

                return false;

            }

            slow = slow->next;

            head = head->next;

        }

      return true;

        

    }