Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

 brute force:

put all the digits in array

check if that is a palindrome or not

optimal: (algo)

1) find middle(slow pointer will be the middle)

2) reverse the right half of the linkedlist

3)move slow pointer by one more step

4)take dummy node and place at the head

5)start traversing both dummy and slow

6)when slow reach null and all are same then its a palindrome

class Solution {
public:
    ListNode* reverselist(ListNode* head){
        ListNode* prev=NULL;
        ListNode* curr=head;
        ListNode* nex=NULL;
        while(curr!=NULL){
            nex=curr->next;
            curr->next=prev;
            prev=curr;
            curr=nex;
        }
        return prev;
    }
    bool isPalindrome(ListNode* head) {
        if(head==NULL || head->next==NULL ) return true;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast->next!=NULL && fast->next->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        slow->next=reverselist(slow->next);
        slow=slow->next;
        
        while(slow!=NULL){
            if(head->val!=slow->val) return false;
            head=head->next;
            slow=slow->next;
        }
        return true;  
    }
};