python - palindrome list - subtle

  • 0
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    # = None
    class Solution(object):
        def isPalindrome(self, head):
            :type head: ListNode
            :rtype: bool
            # this problem cannot be solved in O(1) space complexity
            # you have to remember the elts you saw before in an order
            # different from how they appear in the list, which means
            # you must store them in some info structure. inputs are rd-only !
            # look before you leap
            # head can be null
            l1, l2, l3 = [], head, if head != None else None
            # l3 can be initially null because head can be null
            # or can be null
            while l3 and
                l3 = (
                l2 =
            # l3 can be null in case of an odd-length list
            # or above conditions
            # if len is odd, l3 is None and l2 is middle elt. skip it
            # if len is odd, l3 is valid and l2 is middle elt. consider it
            if l3 != None:
            # tricky details here
            # consider [1]
            # l3 is None, l1 is empty
            # l2 is valid and first elt. move it
            # l2 moves fwd in all cases
            l2 = if l2 != None else None
            while l2 != None:
                if l1.pop() != l2.val:
                    return False
                l2 =
            return True

Log in to reply

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