Delete node at nth position from the end of a list (Leet code problem 19)

Question

I am trying to solve the LeetCode challenge 19. Remove Nth Node From End of List:

Given the head of a linked list, remove the n^th node from the end of the list and return its head.

Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Below is my function. It uses the 2 pointer method. It works fine for many test cases, except this one:

• Linked list = [1,2,3]
• n = 3

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    if head is None or head.next is None:
        return None
    if head.next.next is None :
        if(n ==1):
            head.next = None
            return head
        if(n == 2):
            head = head.next
            return head 
            
    slow_pointer = head 
    fast_pointer = head
    for i in range(n+1):
        fast_pointer = fast_pointer.next
    while(fast_pointer is not None):
        fast_pointer = fast_pointer.next
        slow_pointer = slow_pointer.next
    slow_pointer.next = slow_pointer.next.next
    return head

Where did I go wrong?

Answer 1

Your code does not treat the general case where the head node needs to be removed. At the start it does treat a few such cases (when the size of list is less than 3), but this obviously will not do the trick for larger lists.

The problem is that when n is the size of the list, then this loop will have an error in the last iteration, because it will start with fast_pointer equal to None:

for i in range(n+1):
    fast_pointer = fast_pointer.next

You should therefore deal with that last iteration separately, not as part of this loop. Make the loop one iteration shorter, and perform the last "move" separately, if possible:

for i in range(n):
    fast_pointer = fast_pointer.next
if fast_pointer is None:
    return head.next  # remove first node
fast_pointer = fast_pointer.next

...and then the final part of your code can remain as it is.

With this change, you don't really have to treat that many special cases at the start of your code. In fact, it is given (on LeetCode) that the list will have at least one node. So you actually don't have any boundary cases to deal with.

Applying these changes, your code becomes:

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
    slow_pointer = head 
    fast_pointer = head
    for i in range(n):
        fast_pointer = fast_pointer.next
    if fast_pointer is None:
        return head.next  # remove first node
    fast_pointer = fast_pointer.next
    while fast_pointer is not None:
        fast_pointer = fast_pointer.next
        slow_pointer = slow_pointer.next
    slow_pointer.next = slow_pointer.next.next
    return head