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 = , n = 1
Output: []


Example 3:

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


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.

c++ implementation:

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

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

t->next=t->next->next;
}
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.

c++ implementation:

    ListNode* removeNthFromEnd(ListNode* head, int n)
{
return NULL;

while(n)
{
f=f->next;
n--;
}
if(f==NULL)        //two handle the extra two cases

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