O(n) Time and Not-So-True O(1) space Python Solution, without modifying the list


  • 0
    W
    class Solution(object):
        def isPalindrome(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if head:
                keeper = head
                listk = []
                listk.append(keeper)
                try:
                    self.endReaching(listk, head)
                except:
                    return False
            return True
            
            
        def endReaching(self, listk, anode):
            if anode.next != None:
                self.endReaching(listk, anode.next)
            if listk[0].val != anode.val:
                raise 
            if listk[0].next != None:
                listk[0] = listk[0].next
    

    This solution is very slow comparing to the rest (~16%) but I didn't find a similar solution like this. I'm not sure if I can use such method in a real interview though.... I used try and raise to break out of the recursive function calls. I also went through the whole list because I wasn't patient enough to write my own exceptions to terminate the function half-way. The error handling might be the process slowing this solution down. I know "goto" in C can achieve this too. Is there anything else in Python can achieve a similar effect?


    Well, with second thought, recursive calls might not be regarded as O(1) space....


Log in to reply
 

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