Is this solution O(1) Space?


  • 0
    D

    If I create an variable to store the node values and keeps deleting nodes, is it O(1) space?

    class Solution(object):
        def isPalindrome(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if not head or not head.next:
                return True
            x = [head.val]
            while head and head.next:
                x.append(head.next.val)
                head.next = head.next.next
            
            for k in range(0, len(x)/2 + 1):
                if x[k] != x[-k-1]:
                    return False
            return True

  • 0

    You're not deleting anything, and the caller could have references to all nodes so that the garbage collection doesn't delete, either.


  • 0
    D

    Thanks, right, if the caller keeps references, then those nodes are not deleted. So I have to explicitly 'del' those nodes.


  • 0

    What is using del supposed to achieve?


  • 0
    D

    To achieve O(1) Space


  • 0
    D
    This post is deleted!

  • 0
    D
    class Solution(object):
        def isPalindrome(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            if not head or not head.next:
                return True
            x = [head.val]
            while head and head.next:
                x.append(head.next.val)
                k = head.next
                head.next = head.next.next
                del k
            
            for k in range(0, len(x)/2 + 1):
                if x[k] != x[-k-1]:
                    return False
            return True

  • 0

    I know that that's your goal. What I meant is how is del supposed to help with that?


  • 0

    That del k does absolutely nothing other than deleting the variable k. Since your original didn't even have that variable, this is strictly worse than your original. No advantage whatsoever, but doing extra work for nothing.


  • 0
    D

    Well it is embarrassing. I vaguely thought 'del' would free the memory pointed by 'k', but it really does is to delete variable k itself. I found out sadly that I didn't actually understand the Python variable memory management. Time for self studies now, thank you a lot in spending time here!!


  • 0

    Well at least you learned something :-)

    I guess you could do it in C++, where delete actually does what you intended (unless you don't have permission to delete the nodes, not sure if that's possible). And then in a very weird way I guess you could somewhat claim O(1) space, though I wouldn't. Also, if there are outside pointers to the deleted nodes, they'd become invalid, and that would be dangerous/bad.


  • 0
    D

    Yep, thanks for cheering me up! And you are right, I got it why this is dangerous.


Log in to reply
 

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