Leetcode daily practice - 203. remove linked list elements

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 203. Remove linked list elements

Let’s get it！

---

---

1. Topic analysis

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：

Example 2：

Example 3：

2. Title diagram

The problem is very simple , Or adopt Double pointer Law , But there are several situations to consider

（1） Routine situation
 
（2） There are continuous in the linked list val
 
（3） The head node is val

Routine situation

Define a prev Pointer to NULL; Let me define one more cur The pointer points to the head node

The first 1 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 2 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 3 Step ： here cur The element that points to is equal to 6, So the element 6 Set as NULL, And then let prev Of next Point to elements 3,cur Of next It also points to elements 3 （ As shown in the figure ）

The first 4 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 5 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 6 Step ： here cur The element that points to is equal to 6, So the element 6 Set as NULL, And then let prev Of next Point to cur Of next（ As shown in the figure ）

The first 7 Step ： When cur The element pointed to is empty when , The loop ends （ As shown in the figure ）

Dynamic diagram demonstration

continuity val situation

Or to define a prev Pointer to NULL; Let me define one more cur The pointer points to the head node （ As shown in the figure ）.

The first 1 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 2 Step ：cur The element pointed to is not equal to 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 3 Step ： here cur The element that points to is equal to 6, Then delete the element , And then let prev Of next Point to cur Of next,cur Point to the next element （ As shown in the figure ）

The first 4 Step ： here cur The element pointed to is still equal to 6, Then delete the element , And then let prev Of next Point to cur Of next,cur Point to the next element （ As shown in the figure ）

The first 5 Step ： here cur The element pointed to is still equal to 6, Then delete the element , And then let prev Of next Point to cur Of next,cur Point to the next element （ As shown in the figure ）

The first 6 Step ： here cur The element pointed to is not 6, that prev and cur Move backward in turn （ As shown in the figure ）

The first 7 Step ： here cur The element that points to is equal to 6, Then delete the element and let prev Of next Point to cur Of next,cur Point to empty , End cycle （ As shown in the figure ）

You can see , If there are continuous val, Then the practice is the same as the conventional situation .

The head node is val

Or to define a prev Pointer to NULL; Let me define one more cur The pointer points to the head node （ As shown in the figure ）.

At this point, a problem can be found , If it is calculated according to the normal situation, it is ,cur The element that points to is equal to 6, Then delete the element , And then let prev Of next Point to cur Of next,cur Point to the next element .

But at this time prev The element pointed to is empty , cur Of next How can I assign a value to empty Well ？ Obviously not , We have to find another way ！

It's very simple , Let's define one more curHead The pointer points to the head node （ As shown in the figure ）.

Here, a dynamic diagram is directly used to demonstrate the whole process

3. Code implementation

Interface code

struct ListNode* removeElements(struct ListNode* head, int val){
    
    struct ListNode* prev, *cur;
    prev = NULL;
    cur = head;
    //  The end condition of the loop is cur It's empty 
    while (cur) {
    
        // cur It's not equal to val
        if (cur->val != val) {
    
            prev = cur; // Put... Directly cur Address assigned to prev, Is equivalent to prev Move to cur Location 
            cur = cur->next; // cur Also move one position backwards 
        }
        else {
     //  When cur be equal to val
            struct ListNode* curHead = cur->next; 
            //  Why?  curHead  The content is  cur->next,  instead of cur Well ？
            //  Suppose that the head node is equal to val, Then delete val in the future ,  It is equivalent to header deletion 
            //  After deleting the header , If curHead Yes, the content is cur If you have your address , I can't find the following list for so long 
            //  therefore curHead The deposit should be cur->next,  That is, the address of the second node 
            if (prev == NULL) {
     //  The head node is val by val The situation of 
                free(cur); //  release cur
                head = curHead; //  Update the header node 
                cur = curHead; //  Then assign the address of the new head node to cur
            }
            else {
     //  The header node is not val by val The situation of 
                free(cur); //  Release val Elements 
                prev->next = curHead; //  because curHead Deposit is cur Of next, That is to say cur The address of the next node , So it is directly assigned to prev Of next
                cur = curHead; //  And then let cur Point to the address of the next node 
            }
        }
    }
    return head;
}

Submit results