234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow-Up:

Could you do it in $O(n)$ time and $O(1)$ space?

Solution:

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        middle = self.get_middle(head)
        tail = self.reverse(middle)
        while tail and head:
            if tail.val != head.val:
                return False
            tail = tail.next
            head = head.next
        return True

    def get_middle(self, head):
        if not head or not head.next:
            return head
        slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverse(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre, cur = cur, nxt
        return pre