I try to figure out how to return value from the bottom of the recursive stack.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    kth = -1
    def helper(curr, prev, length):
        if not curr:
            return length - n

        length  = 1
        kth = helper(curr.next, curr, length)

        if length == kth:
            prev.next = curr.next

    dummy = head
    helper(head, None, 1)
    return dummy

The first stack unwind set the kth value, next will be None. I can't figure out how to pass it forward to the top.

I understand why it works in that way, only seek for resolution. Not explanation.

CodePudding user response：

There are more memory efficient solutions, but if you want to do it this way, then:

1. There is no return statement that is executed except in the base case, this means that a caller will get None from the recursive call, except for one time.

2. There is no need to pass more than the second argument to helper, i.e. prev. curr can be derived from it, and the length parameter is not needed: you can return n in the base case, and decrease that value as you backtrack.

3. The idea of a dummy is nice, but then the idea is that it is a new node that precedes head in the extended linked list. Making only a synonym for head brings you nothing useful.

Here is your code with those three issues fixed:

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def helper(prev):
            if not prev.next:
                return n

            i = helper(prev.next) - 1

            if i == 0:
                prev.next = prev.next.next
            return i

        dummy = ListNode(0, head)
        helper(dummy)
        return dummy.next