Nowcode- learn to delete duplicate elements in the linked list (detailed explanation)

Preface

‍ There's a long way to go

One 、 Delete the link of repeated node questions in the linked list

Title Description

Delete the duplicate elements in the given linked list （ The elements in the linked list are ordered from small to large ）, Make all elements in the linked list appear only once
for example ：
The list given is 1→1→2, return 1→ 2.
The list given is 1→1→2→3→3, return 1→2→3.

The test sample 1:

Input {1,1,2}
Return value {1,2}

The test sample 2:

Input {1,1,1}
Return value {1}

The test sample 3:

Input {}
Return value NULL

Topic ideas

1. Repetition means that at least two of them are the same , So use two pointers , Slow pointer and fast pointer respectively .
2. The slow pointer points to the head node , The fast pointer points to the second node .
3. Compare the slow pointer with the fast pointer , If different , The pointer goes in one , If the same , Quick pointer into one , Then compare .

Be careful ：

First judge whether the broken node is NULL;

Pictured ：

The code is as follows ：

class Solution {
    
public:
    /** * * @param head ListNode class  * @return ListNode class  */
    ListNode* deleteDuplicates(ListNode* head) 
    {
    
        // write code here
        if(head==NULL)
            return NULL;
        struct ListNode*fast=NULL;
        struct ListNode*slow=NULL;
        slow=head;
        fast=head->next;
        while(fast)
        {
    
            if(fast->val!=slow->val)
            {
    
                fast=fast->next;
                slow=slow->next;
                
            }
            else
            {
    
                slow->next=fast->next;
                fast=fast->next;
                
            }
        }
        return head;
    }
};

Two 、 Delete the repeated element question links in the linked list

Title Description

In a sorted list , There are duplicate nodes , Please delete the duplicate nodes in the list , Duplicate nodes are not reserved , Return chain header pointer .
for example , Linked list 1->2->3->3->4->4->5 After treatment: 1->2->5

The test sample 1：

Input {1,2,3,3,4,4,5}
Return value {1,2,5}

The test sample 2：

Input {1,1,1,1,1}
Return value NULL

Topic ideas

1. This is to delete duplicate elements , So use four pointers , One Quick pointer fast

2. One Slow pointer slow

3. One more Sentinel position pointer guard To receive the address of the newly opened space , The newly opened space is the sentry post , Used to connect linked lists

4. the other one The pointer newhead Always point to the newly opened space , Used to remember the header node

5. Use the sentry position to point to the head node first

6. slow Point to the head node ,fast Point to the second node ,guard Point to the sentry post ,newhead Always point to the sentry .
   

7. Compare slow and fast, Different things go into one , identical ,fast Jin Yi

8. Last slow And fast At different times ,guard We need to be connected fast,slow To point to fast,fast One more step

Be careful ：

1. First judge pHead Is it empty
2.fast Go straight ahead , Walk about NULL The situation of

Pictured ：

The code is as follows ：

class Solution {
    
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
    
        if(pHead==NULL)
        {
    
            return pHead;
        }
// struct ListNode*slow=NULL;
        struct ListNode*fast=NULL;
        struct ListNode*slow=NULL;
        struct ListNode*guard=NULL;
        struct ListNode*newhead=NULL;
        guard=(struct ListNode*)malloc(sizeof(struct ListNode));
        newhead=guard;
        guard->next=pHead;
        fast=pHead->next;
        slow=pHead;
        while(fast)
        {
    
            if(slow->val!=fast->val)
            {
    
                fast=fast->next;
                slow=slow->next;
                guard=guard->next;
            }
            else
            {
    
               while(slow->val==fast->val&&fast!=NULL)
               {
    
                   fast=fast->next;
               }
               if(fast==NULL)
               {
    
                   guard->next=NULL;
                   return newhead->next;
               }
                guard->next=fast;
                slow=fast;
                fast=fast->next;
                
            }
        }
        
        return newhead->next;
    }
};

summary

I hope you have your own harvest , Thank you for the compliment