19. Remove Nth Node From End of List

Description

See: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Solution

I used the runner technique to solve this problem. I move the runner forward n times. Then I move both the walker and runner together at the same time. When the runner gets to the end of the linked list, the walker will be at the node prior to the node to be removed. Then it is a matter of updating the walker's next pointer.

My first version was messier than this. I had one while loop and a counter I incremented in it. If the counter was greater than n then I would move the walker. It worked, but this is tidier.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        walker = runner = head
        
        # move the runner forward the n spots. This will leave a gap between the walker
        # and runner of the desired "back n elements"
        for i in range(n):
            runner = runner.next
        
        # Handles the case where n is the same size as the linked list. The runner reaches 
        # the end of the linked list, so just return the head's next item.
        if not runner:
            return head.next
        
        # Now move runner through the rest of the linked list, walker moves along too
        while runner.next:
            runner = runner.next
            walker = walker.next
        
        # Remove the "nth node from the end of the list" by updating the prior node's
        # next pointer                
        walker.next = walker.next.next
        return head