Python Solution Time: O(n), Space: O(1) with Comments


  • 0
    M
        def isPalindrome(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if not head or not head.next:
                return True
            
            # Count the linked list
            count = 0
            curr = head
            while curr:
                count += 1
                curr = curr.next
            
            # Reverse half of the linked list
            i = 0
            curr = head
            prev = None
            while curr and i != count / 2:
                next = curr.next
                curr.next = prev
                prev = curr
                curr = next
                i += 1
            
            # Skip middle value
            if count % 2:
                curr = curr.next
            
            # Compare reversed first half with the second half
            head = prev
            while i:
                if head.val != curr.val:
                    return False
                head, curr = head.next, curr.next
                i -= 1
            return True
    

Log in to reply
 

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