234. Palindrome Linked List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    bool check(vector<int>& arr)
    {
        int e = arr.size()-1;
        int s = 0;
        while(s < e)
        {
            if(arr[s] != arr[e])
                return false;
            s++;
            e--;
        }

        return true;
    }

    ListNode* getMid(ListNode* head)
    {
        ListNode* slow = head;
        ListNode* fast = head -> next;
        while(fast != NULL && fast -> next != NULL)
        {
            fast = fast -> next -> next;
            slow = slow -> next;
        }

        return slow;
    }

    ListNode* reverse(ListNode* head)
    {
        ListNode* curr = head;
        ListNode* next = NULL;
        ListNode* prev = NULL;

        while(curr != NULL)
        {
            next = curr -> next;
            curr -> next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

    bool isPalindrome(ListNode* head) {
                //Approach 1. 
        // if(head -> next == NULL)
        //     return true;
        // vector<int> arr;
        // ListNode* temp = head;

        // while(temp != NULL)
        // {
        //     arr.push_back(temp -> val);
        //     temp = temp -> next;
        // }

        // return check(arr);


                //Approach 2.
        
        if(head -> next == NULL)
            return true;
        
        //step 1. find middle node
        ListNode* middle = getMid(head);

        //step 2. reverse the list from middle ->next
        ListNode* temp = middle -> next;
        middle -> next = reverse(temp);

        // step 3. compare both halves
        ListNode* head1 = head;
        ListNode* head2 = middle-> next;

        while(head2 != NULL)
        {
            if(head2 -> val != head1 -> val)
                return false;

            head1 = head1 -> next;
            head2 = head2 -> next;
        }

        //step 4. repeat step 2 to make the LL as input
        temp = middle -> next;
        middle -> next = reverse(temp);
        return true;
    }
};