def isPalindrome(head):
def reverse(head):
"""Abdul Bari's solution"""
front, mid, back = head, None, None
while front:
front, mid, back = front.next, front, mid
mid.next = back
return mid
def middleNode(head):
mid_prev = None
slow = fast = head
while fast and fast.next:
mid_prev = slow
slow, fast = slow.next, fast.next.next
return slow, mid_prev
middle_node, mid_prev = middleNode(head)
last_node = reverse(middle_node)
result = True
a, b = head, last_node
while a and b:
if a.val != b.val:
result = False
break
a, b = a.next, b.next
if mid_prev:
mid_prev.next = reverse(last_node)
return result