Title Description

I'll give you a list , Delete the last of the linked list n Nodes , And return the head node of the list .
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]

Advanced ： Can you try a scan implementation ？

Their thinking

1. Two iterations , First record penultimate N A position in the positive order of the linked list . But traversed the linked list twice .

ListNode* removeNthFromEnd(ListNode* head, int n) {
    
    ListNode *p=head;
	ListNode *r=head;
	int i=0;
	while(p){
    // Record the total length of the linked list 
		i++;
		p=p->next;
	}
    if(i==n){
    // A special case   Deleting the last element is the first element in positive order 
		head=head->next;
		return head;
	}
	int j=i-n,k=1;//  Last but not least N The first element is in positive order j A place 
	while(k<j){
    
		r=r->next;
		k++;
	}
	p=r->next;// Cover directly 
	r->next=p->next;
	return head;
    }

2. Use the speed pointer （ Double pointer ） Traverse , First use the fast pointer to move forward N Nodes , Then move the fast and slow pointer together , Until the fast pointer traverses to the last node , The slow pointer is the penultimate N+1 Nodes .

 N + X =Length 
 // N It's the number of steps the pointer takes at the beginning ,X Indicates the number of steps followed by the fast and slow pointers .
 // The slow pointer only goes X Step , also N The first step is not finished , That is to say, we have reached the penultimate N+1 Nodes .

ListNode* removeNthFromEnd(ListNode* head, int n) {
    
	ListNode *pre=new ListNode(0);// Set a virtual node 
	pre->next=head;
	ListNode* fast=pre;// Quick pointer 
	ListNode* slow=pre;// Slow pointer 
	while(n--){
    // Let the pointer go first N Step 
		fast=fast->next;
	}
	while(fast->next){
    // Go with the hands 
		slow=slow->next;
		fast=fast->next;
	}
	ListNode* tmp=slow->next;// Form a good habit of releasing nodes 
	slow->next=slow->next->next;
	delete tmp;// Form a good habit of releasing nodes 
	return pre->next;// Notice the returned representation 
}

Don't look, there are two while Just traversed twice , Look carefully, the fast pointer only traverses once , Of course, it can be put in a while in , The purpose of writing is to make it easier for readers to understand .