Leetcode 234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

The task is easy, while O(1) space needs some thinking. We can get the length, then how to check? Because there is no way back in single linked list, we should reverse the first or last half and then do the check. Restoring the list is optional.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        reverse, fast = None, head
        while fast and fast.next:
            fast = fast.next.next
            head.next, reverse, head = reverse, head, head.next

        # If the number of the nodes is odd,
        # set the head of the tail list to the next of the median node.
        tail = head.next if fast else head

        # Compare the reversed first half list with the second half list.
        # And restore the reversed first half list.
        is_palindrome = True
        while reverse:
            is_palindrome = is_palindrome and reverse.val == tail.val
            reverse.next, head, reverse = head, reverse, reverse.next
            tail = tail.next

        return is_palindrome

Run Time: 136 ms