python - palindrome list - subtle


  • 0
    S
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = 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, head.next if head != None else None
            
            # l3 can be initially null because head can be null
            # or head.next can be null
            while l3 and l3.next:
                l3 = (l3.next).next
                l1.append(l2.val)
                l2 = l2.next
            
            # 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:
                l1.append(l2.val)
            
            # 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 = l2.next if l2 != None else None
            
            while l2 != None:
                if l1.pop() != l2.val:
                    return False
                l2 = l2.next
            
            return True
    

Log in to reply
 

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