<p>Given the <code>head</code> of a singly linked list, return <code>true</code><em> if it is a </em><span data-keyword="palindrome-sequence"><em>palindrome</em></span><em> or </em><code>false</code><em> otherwise</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg" style="width: 422px; height: 62px;" />
<pre>
<strong>Input:</strong> head = [1,2,2,1]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg" style="width: 182px; height: 62px;" />
<pre>
<strong>Input:</strong> head = [1,2]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the list is in the range <code>[1, 10<sup>5</sup>]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 9</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Could you do it in <code>O(n)</code> time and <code>O(1)</code> space?
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        def reverse(head):
            prev,cur = None,head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True

















        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True













        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head and head2:
            if head.val !=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True















        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val != head2.val:
                return False

            head = head.next
            head2 = head2.next
        return True













        def mid(head):
            slow,fast = head,head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val !=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True















        def mid(head):
            slow,fast=head,head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val !=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True













        def mid(head):
            slow,fast = head,head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True















        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            prev,cur = None,head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head2.val!=head.val:
                return False
            head2 = head2.next
            head = head.next
        return True




















        def mid(head):
            slow,fast = head,head.next
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            prev,cur = None,head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head2 and head:
            if head2.val != head.val:
                return False
            head2 = head2.next
            head = head.next
        return True
















        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True


















        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev

        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True



















        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            prev,cur = None,head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True























        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            prev = None
            cur = head
            while cur:
                tmp = cur.next
                cur.next = prev

                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head2 and head:
            if head2.val!=head.val:
                return False
            head2 = head2.next
            head = head.next
        return True























        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head2 and head:
            if head2.val!=head.val:
                return False
            head2 = head2.next
            head = head.next
        return True




























        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head2 and head:
            if head2.val!=head.val:
                return False
            head2 = head2.next
            head = head.next
        return True

































        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        head2 = reverse(mid(head))
        while head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True






































        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow

        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True





































        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head2 and head:
            if head2.val != head.val:
                return False
            head2 = head2.next
            head = head.next
        return True






































        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow= slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head2 and head:
            if head.val !=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True
















































        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            prev,cur = None,head
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev
        head2 = reverse(mid(head))
        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True





































        def mid(head):
            slow,fast = head,head 
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev

        head2 = reverse(mid(head))
        while head and head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True














































        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow

        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev

        head2 = reverse(mid(head))
        while head and head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True





























        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow

        def reverse(head):
            cur,prev = head,None
            while cur:
                tmp = cur.next
                cur.next = prev
                prev = cur
                cur = tmp
            return prev

        head2 = reverse(mid(head))

        while head and head2:
            if head.val!=head2.val:
                return False
            head = head.next
            head2 = head2.next
        return True







































        def mid(head):
            slow,fast = head,head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            return slow
        def reverse(head):
            cur,prev = head,None
            while cur:
                temp = cur.next
                cur.next = prev
                prev = cur
                cur = temp
            return prev
        
        head2 = reverse(mid(head))
        
        while head and head2:
            if head.val != head2.val:
                return False
            head = head.next
            head2 = head2.next
        
        
        return True
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        l,r=0,len(nums)-1
        while l<=r:
            if nums[l]!=nums[r]:
                return False
            l=l+1
            r=r-1
        return True
            
            
        
28628