LeetCode203. Remove linked list elements

LeetCode203. Remove linked list elements

1. subject

2. Ideas

The overall idea is to delete nodes , But there are two ways to realize it .

（1） Do not use sentinel nodes
Relatively speaking, it is more complicated , Because it's not good to manage header nodes , There are two ways of thinking .
a. At the beginning, the special judgment head node , Time complexity is high .
b. Finally, determine the head node .

(2) Use the header node

3. Specific code implementation

Create linked lists and function interfaces

 struct ListNode {
    
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {
    }
     ListNode(int x) : val(x), next(nullptr) {
    }
     ListNode(int x, ListNode *next) : val(x), next(next) {
    }
 };
 
class Solution {
    
public:
    ListNode* removeElements(ListNode* head, int val) {
    
    } };

Do not use sentinel nodes

（1） First special judgment header node

class Solution {
    
public:
    ListNode* removeElements(ListNode* head, int val) {
    
         ListNode* p =head; // Point to the head node  
    	 // Special judgment head node  
    	 while(p!= NULL && p->val == val)
    	 {
    
    	 	ListNode* m =p;
    	 	head = head->next;
    	 	p = p->next;
    	 	delete m;
		 }
    	if(head == NULL) return nullptr;//1.NULL still nullptr？ All the 
    	
        ListNode* q =head; // Point to the head node   Fixed ！  And certainly not to be deleted  
		while(q != NULL && q->next != NULL)//2.q!=NULL Don't write it ？ Sure 
		{
    
			if(q->next->val == val)
			{
    
				ListNode* n = q->next;
				q->next = n->next;  // Connect the linked lists  
				delete n;
			}
			else// This can't be lost 
			q = q->next;
		}
		return head;
       
    }
};

matters needing attention

1.return NULL/nullptr/head It's all right .
2. When q When the position pointed to is not sure whether it really exists, you can't just write q->next != NULL , Must be right q There is also judgment in the direction of .
3. When deleting nodes, you should not forget to connect the linked lists

（2） Finally, determine the head node

class Solution {
    
public:
    ListNode* removeElements(ListNode* head, int val) {
    
 		ListNode* p =head; // Point to the head node  
		ListNode* m =head; // Point to the head node 
		
		while(p!= NULL && p->next != NULL)//1. Can't be without p！=NULL  It doesn't judge whether the current pointer is meaningful ！
		{
    
			if(p->next->val == val){
    
				ListNode* q =p->next;
				p->next = q->next;
				delete q;}
			else
				{
    p = p->next;}	
		} 
		 Special judgment head node 
		if(head != NULL && head->val == val)// Finally, determine the head node   It is not empty and the value is val
		{
    
			if(head->next != NULL)// There are elements after the header node 
			{
    
				head = head->next;
				delete m;
				return head;
			}
			else// There is no element after the header node 
			{
    
                delete head;
                return head;//2. Here it's changed to NULL also nullptr Fine 
			}
		}
        else// The head node is empty 
        return head;
   }
  };

matters needing attention

1. Be sure to judge whether the current pointer is meaningful ！
2.return head Here it's changed to NULL also nullptr Fine

Use sentinel nodes

class Solution {
    
public:
  ListNode* removeElements(ListNode* head, int val) {
    
     // Set up a sentinel node 
	  ListNode* dummyHead = new ListNode(0); 
      dummyHead->next = head;// Point to the head node 
      ListNode *p = dummyHead;
      
		while(p->next!= NULL)
		{
    
			if(p->next->val == val)
			{
    
				ListNode *q = p->next;
				p->next = q->next;
				delete q;
			}else
			p = p->next;
		} 
		
       head = dummyHead->next;// I don't know  
       delete dummyHead;// No delete It's OK   Habit should delete
       return head;
    }
};

matters needing attention

1. Using sentinel nodes should release ！ This habit is better ！
2.dummyHead The creation of ：( according to struct The function in ）

//1.
ListNode* dummyHead = new ListNode(0); 
dummyHead->next = head;// Point to the head node 

//2.
ListNode *dummyHead = new ListNode(0,head);// At the same time, specify its value and pointer to  

//3.  You can also specify the direction first and then the value .