#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def isPalindrome(self, head):
    if head and head.next is None:
      return True
    slow, fast = head, head
    prev = slow
    # Classic fast and slow to get to middle of list
    while fast and fast.next:
      prev = slow
      slow = slow.next
      fast = fast.next.next
    # If fast is not None, that means list is odd and we can ignore the middle number
    # (ie: 1, 2, 3, 2, 1) -> we could ignore 3
    if fast:
      slow = slow.next
    # We do this because we don't care about anything after first half and we already have pointer to second half
    prev.next = None
    # reverse from slow on
    current = slow
    reverse = None
    # This is how to reverse second half of list
    while current:
      n = current.next
      current.next = reverse
      reverse = current
      current = n
    # Simply confirm equality until they are both None
    while head and reverse and head.val == reverse.val:
      head = head.next
      reverse = reverse.next
    # Confirm they are both None
    return head is None and reverse is None
    
  def printList(self, head):
    stack = []
    while head:
      stack.append(str(head.val))
      head = head.next
    print("->".join(stack))