# 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  # 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
python - palindrome list - subtle
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.