current position:Home>leedcode. 203 remove linked list elements

leedcode. 203 remove linked list elements

2022-04-29 19:40:58Two ball Sycamore

List of articles

First knowledge of single linked list



Give you a list of the head node head And an integer val , Please delete all the contents in the linked list Node.val == val The node of , And back to New head node .
Example 1:
 Insert picture description here

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

Example 2:

Input :head = [], val = 1

Output :[]

Example 3:

Input :head = [7,7,7,7], val = 7

Output :[]

Method 1 : I'll delete what I should delete

When you meet Node.val==val when ,
 Insert picture description here
In order to cur Node removal ,cur The previous node of prev Should be stored cur The address of the last node of ,free Use the deleted node , also cur Move back a bit .
 Insert picture description here
When Node.val != val when ,prev and cur All moving back ,
After traversal, you can delete .

struct ListNode* removeElements(struct ListNode* head, int val){
    
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
 {
    
    if(cur->val == val)
    {
    
        prev->next = cur->next;
        free(cur);
        cur = prev->next;
    }
    else
    {
    
        prev = cur;
        cur = cur->next;
    }  
 }
    return head;
}

 Insert picture description here
Wrong spicy !
Let's look at execution use cases ,7,7,7,7,
Create another 1,7,7,7
 Insert picture description here
It seems to be the problem of header deletion , Then add a header and delete .

struct ListNode* removeElements(struct ListNode* head, int val){
    
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
 {
    
    if(cur->val == val)
    {
    
    	// Header deletion is handled separately 
        if(cur==head)
        {
    
            head = cur->next;
            free(cur);
            cur = head;
        }
       else
       {
    
        prev->next = cur->next;
        free(cur);
        cur = prev->next;
        }
    }
    else
    {
    
        prev = cur;
        cur = cur->next;
    }  
 }
    return head;
}

Method 2 : What shouldn't be deleted, I'll stay

Go through it , It's not val Tail insertion .
 Insert picture description here
The code is as follows :

struct ListNode* removeElements(struct ListNode* head, int val){
    
    struct ListNode* tail = NULL;
    struct ListNode* cur = head;
    head = NULL;
    while(cur)
 {
    
    if(cur->val == val)
    {
    
      struct ListNode* del = cur;
      cur = cur->next;
      free(del);
        
    }
    else
    {
    
       // Tail insertion 
        if(tail == NULL)
        {
    
            head = tail = cur;
        }
        else
        {
    
            tail->next = cur;
            tail = tail->next;
        }
        cur = cur->next;
    }  
 }
    if(tail)
        tail->next = NULL;
    return head;
}

That's all for today's sharing .
 Insert picture description here


copyright notice
author[Two ball Sycamore],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/119/202204291757346317.html

Random recommended