234. Palindrome Linked List Leetcode Solution

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast -> next != NULL) {
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        if (fast != NULL && fast -> next == NULL) slow = slow -> next;
        ListNode* prv = NULL;
        ListNode* tmp = NULL;
        while (slow != NULL) {
            tmp = slow -> next;
            slow -> next = prv;
            prv = slow;
            slow = tmp;
        }
        slow = prv, fast = head;
        while (slow && fast) {
            if (slow -> val != fast -> val) return false;
            slow = slow -> next;
            fast = fast -> next;
        }
        return true;
    }
};

class Solution {
    public boolean isPalindrome(ListNode head) {
        // init arraylist and store linkedlist vals
        List< Integer> list = new ArrayList();
        for(ListNode curr=head; curr != null; curr=curr.next){
            list.add(curr.val);
        }
        // two pointer search
        int start = 0;
        int end = list.size()-1;
        while(start <= end){
            // if first and last vals are not same it's not palindrome
            if(list.get(start) != list.get(end)) return false;
            start++;
            end--;
        }
        // if above condition doesn't hit means it's a palindrome
        return true;
    }
}

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        global front
        front = head

        def helper(back) -> bool:
            global front
            if not back:
                return True

            #let back pointer travel to the back of the list through recursion
            equal_so_far = helper(back.next)

            #check if front and back have the same value
            value_equal = (front.val == back.val)

            #when the function return, back is gradually moved toward head of the list
            #move front accordingly to compare their value
            front = front.next
            return equal_so_far and value_equal
        
        return helper(head)