Leetcode[234] Palindrome Linked List

234. Palindrome Linked List

recursion not work, stack will be overflow

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
       
        def check(head):
            if not head:
                return True
            ret=check(head.next) & self.temp.val==head.val
            self.temp=self.temp.next
            return ret
            
            
        self.temp=head       
        return check(head)

using iterative way

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        #find the middle
        f=head
        s=head
        pre=s
        if not head or not head.next:
            return True
        while f and f.next:
            f=f.next.next
            s=s.next
        
        
        #reverse the latter half,now we find a middle node, it can be aabaa pattern or acca pattern, here is a trik, mark the middle.next=None,
        #b.next=None or c.next=None
        pre=None
        while s:
            t=s.next
            s.next=pre
            pre=s
            s=t
        while pre:
            if pre.val!=head.val:
                return False
            pre=pre.next
            head=head.next
        return True