Remove Nth Node From End of List

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

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

method1 

Two pass algorithm:

count number of elements in linked list, ie. c in below code
than take a pointer t and point it to head ,now traverse again till c-n-1 ,the t pointer will reach one step back of the node to be deleted. so we relink the t pointer as t->next=t->next->next.

extra case which should be taken care of:
if the given n is equal to the number of elements in the linked list ie. the head should be deleted.

we can get to know about this above case by checking if c==n, return head->next;

c++ implementation:

    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
           ListNode*temp=head; int c=1;
    //this below loop to find the no. of elements in linked list
    while (temp->next!=NULL)
    {
        temp=temp->next;
        c++;
    }
    ListNode*t=head;
   if(c==n)
      return head->next;

    for(int i=0;i<c-n-1;i++)
    {
         t=t->next;
    }

     t->next=t->next->next;
        return head;
    }

Time Complexity: O(2L)  ≈ O(L)

space Complexity: O(1)  

where L is the length of the linked list 

method 2:

one pass algorithm:

The fast pointer advances the list by $n+1$ steps from the beginning, while the second slow pointer starts from head. when the fast pointer reaches the end of the list. the slow pointer will reach one step back of the node to be deleted. so we relink the next pointer of the node referenced by the slow pointer to point to the node's next next node. ie. slow->next=slow->next->next.

extra case which should be taken care of:
if the given n is equal to the number of elements in the linked list ie. the head should be deleted.

after has reached n+1 steps,we can get to know about this above case by checking if f==NULL, return head->next.

c++ implementation:

    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
        if(head->next==NULL)
          return NULL;
        ListNode*s=head;
        ListNode*f=head;
        
         while(n)
        {
            f=f->next;
            n--;
        }
        if(f==NULL)        //two handle the extra two cases   
         return head->next;

        while(f->next!=NULL)
        {
            f=f->next;
            s=s->next;
        }
        s->next=s->next->next;
        return head;
    }

Time Complexity: O(L)  

space Complexity: O(1)  

where L is the length of the linked list