Leetcode19. Delete the penultimate node of the linked list [double pointer]

LeetCode19. Delete the last of the linked list N Nodes

1. subject

2. Ideas

1. My own thinking is very simple and rough , Namely :
（1） Find the length of the linked list （2） Change the reciprocal into a positive number by calculation （3） Delete node
Pay attention to the special judgment header ！！ It is convenient to use sentinel nodes to handle header nodes ！！
2. Simplified edition —— With two pointers , Just one scan
The following are implemented respectively .

3. Code implementation

（1） Reverse sequence to positive sequence

class Solution {
    
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    
   	    int size = 0;// Chain length 
		ListNode* dummyHead = new ListNode(-1,head);// Sentinel node 
		ListNode* p = dummyHead;
		
		while(p->next!= NULL)// First traversal ： Statistical list length  
		{
    
			p = p->next;
			size++;	// Chain length  
		} 
		
		int a = size-n+1;// The location of the positive order of the node to be deleted   from 1 Start ！！ 
		if(a == 1)// Special judgment head node 
		{
    
			ListNode*q = head;
			dummyHead->next = head->next;
			head = head->next;// Connecting nodes 
			delete q;
            delete dummyHead;
			return head;
		}
		else// Other situations 
		{
    
			ListNode *q = dummyHead;
			// Start from the sentinel node   Just go   The positive order of the node to be deleted -1  Step by step 
			int cnt = size-n;
			while(cnt--)// Second traversal 
				q = q->next;
			ListNode *m = q->next;
			q->next = m->next;// Connecting nodes 
			delete m;
            delete dummyHead;
			return head;
		}
    }
};

matters needing attention

1. Pay attention to the topic condition ：n It must be size Within the scope of
2. A little summary , I feel like I think about it every time I'm here , It's a bit of a waste of time ：
Statistical list length , If you start from the sentinel node, use
while(p->next!= NULL)
Starting from the beginning is
while(p != NULL)

（2） Double pointer

The most important thing is to omit the steps of calculating the length of the linked list ！！ There is no need to judge the head node ！！
Implementation point ：1. Sentinel node 2. Double pointer
See notes for ideas ：

class Solution {
    
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    
		ListNode* dummyHead = new ListNode(-1,head) ;
		ListNode* fast = dummyHead;// Quick pointer 
		ListNode* slow = dummyHead;// Slow pointer 
		int a = n+1;
		//1. Let's go first n+1 Step —— In order to synchronize the time in the later stage slow Point to the previous node to be deleted , Convenient operation 
		while(a--)
		fast = fast->next;// Back ward n+1 Step 
	
	   //2. The speed pointer moves synchronously ,
		while(fast!=NULL)
		{
    
			slow = slow->next;
			fast = fast->next;
		} // here slow Point to the previous node of the node to be deleted  
		
		//3. Delete operation 
		ListNode*p = slow->next;
		slow->next = p->next;
		delete p;
		return dummyHead->next; // Note that there ！
    }
};

1. Special attention should be paid to the last sentence
return dummyHead->next;
Because the original head node head May have been deleted , The new head node is dummyHead->next.
2.n The value of must be reasonable , So don't think too much ！ There will be no empty fingers ！