Python 52ms recursive solution with O(n) time, O(n) space


  • 0
    J
        def remove_nth_from_end(self, head, n):
            if n == self.place_to_end(head, None, n):
                head = head.next
            return head
            
        def place_to_end(self, node, previous, n):
            if node.next is None:
                place = 1
            else:
                place = 1 + self.place_to_end(node.next, node, n)
            if place == n:
                if previous is not None:  # node is not head
                    previous.next = node.next
            return place

  • 0

    This isn't O(1) space but O(m), where m is the length of the list. Recursion doesn't magically come for free. At least not in Python.


  • 0
    J

    Thanks for pointing this out. I have updated it.


Log in to reply
 

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