234. Palindrome Linked List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def checkListPalindrome(myList: List[int]) -> bool:
    length = len(myList)
    if length <= 1:
        return True
    i = 0
    j = length-1
    while i<j:
        if myList[i] != myList[j]:
            return False

        i += 1
        j -= 1

    return True

class Solution:
    def isPalindrome1(self, head: Optional[ListNode]) -> bool:
        myList = []

        while head:
            myList.append(head.val)
            head = head.next

        return checkListPalindrome(myList)

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        """Gut feeling that I have to use fast and slow pointers"""
        slow = fast = head
        head.prev = None

        while fast and fast.next:
            prevSlow = slow
            slow = slow.next
            fast = fast.next.next

            # set the prev so that we can later go backwards
            slow.prev = prevSlow


        middle = slow

        if not fast:
            # even nodes, slow is middle - right
            middleRight = slow
            middleLeft = slow.prev
            right = middleRight
            left = middleLeft
            while right and left:
                if not (right.val == left.val):
                    return False

                right = right.next
                left = left.prev

            return True

        elif not fast.next:
            # odd nodes, slow is middle
            middle = slow
            left = right = middle
            while left and right:
                if not (right.val == left.val):
                    return False

                right = right.next
                left = left.prev

            return True