<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:
        '''
        Approach 2: O(1 space).
        Cant be recursive - stack will be O(n).
        slow and fast pointers, when reaching the end we are in the middle of the list.
        then reverse from middle to end the array and check start of linked list with the 2nd reversed list. 
        - if one half is n//2 and the other is n//2 + 1 than we don't need to acount for the extra node.
        '''
        if not head: return True
        if not head.next: return True
        slow = fast = head

        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        '''
        now the slow is in the middle. from here we want to reverse the 2nd half
        FIRSTHALF->A(slow)->B->C
        prev = None
        curr = A
        Iteration 1:
            next_node = B    
            curr.next = None == None<-A(slow) B->C->None
            prev = A (curr) 
            curr = B (temp)
        Iteration 2:
            next_node = C
            curr.next = prev(A) == None<-A(slow)<-B C->None
            prev = curr (B)
            curr = next_node (C)
        Iteration 3:
            next_node = None
            curr.next = prev(B) == None<-A(slow)<-B<-C None
            prev = curr (C)
            curr = next_node (None)
        end-of-loop

        - prev is the start of the new reversed list
        '''
        
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        half1 = head
        half2 = prev
        while half2:
            if not half1 and half2: break
            val1 = half1.val
            val2 = half2.val
            if val1 != val2: return False
            half1 = half1.next
            half2 = half2.next
        return True
23203