Python recursive O(n) time / O(1) space


  • 0
    F
    def isPalindrome(self, head):
        if not head or not head.next: return True
        if not head.next.next:
            if head.val==head.next.val:return True
            return False
        length=0
        headCopy=head
        while headCopy:
            length+=1
            headCopy=headCopy.next
        return self.comp(head,length,0)
        
    def comp(self,node,length,i):
        if i==(length-1)/2:
            if length%2==1: return node.next
            else:
                if node.val==node.next.val:
                    return node.next.next
                else:
                    return False
        counterNode=self.comp(node.next,length,i+1)
        if not counterNode:
            return False
        if node.val==counterNode.val:
            if i==0: return True
            return counterNode.next
        return False

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.