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

Here is a javascript solution.

we can solve this with "two pointer" way.

Pseudocode

1. initialize both right and left pointer at head of the list.

2. move the right n times in the list once.

3. now if the right is not null then start moving both left and right one step ahead. (the difference between right and left should be n, in this way we can figure out the nth element from the end).

4. if the right or right.next is null then remove the left element.

   var removeNthFromEnd = function(head, n) { let left= right= head;

    for(i=0; i<n;i++){
        right = right.next;   
    }
   
    if(!right) return head.next;
   
    while(right.next){
        right = right.next;
        left = left.next;
    }
    left.next = left.next.next;
   
    return head;
   

   };

Answer 2

class Solution:
    def remove(self,head:ListNode,n:int)->ListNode:
        dummy=ListNode(0,head)
        # pay attention that left starts at dummy
        left=dummy
        right=head
        # this makes sure, right is n step ahead of left
        while n>0 and right:
            right=right.next
            n-=1
        # when right reaches the end, left would be the previous of the node that we delete
        # that is why left started at dummy node
        while right:
            left=left.next
            right=right.next
        # now delete it
        left.next=left.next.next
        return dummy.next

Answer 3

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