nowcode-学会删除链表中重复元素两题(详解)

前言

‍路还长

一、删除链表中重复节点题的链接

题目描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→ 2.
给出的链表为1→1→2→3→3,返回1→2→3.

测试样例1:

输入 {1,1,2}
返回值{1,2}

测试样例2:

输入{1，1，1}
返回值{1}

测试样例3:

输入{}
返回值NULL

题目思路

1. 重复就是最少得有两个相同，所以用两个指针，分别为慢指针和快指针。
2. 慢指针指向头节点，快指针指向第二个节点。
3. 用慢指针与快指针比较，如果不同，指针都进一，如果相同，快指针进一，接着比较。

注意：

先判断头节点是否为NULL;

如图：

代码如下：

class Solution {
    
public:
    /** * * @param head ListNode类 * @return ListNode类 */
    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;
    }
};

二、删除链表中重复的元素题链接

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

测试样例1：

输入 {1,2,3,3,4,4,5}
返回值{1,2,5}

测试样例2：

输入{1，1，1，1，1}
返回值NULL

题目思路

1. 这个是删除重复的元素，所以用四个指针，一个快指针fast

2. 一个慢指针slow

3. 还有一个哨兵位指针guard来接收新开辟空间的地址，新开辟的空间为哨兵位，用来连接链表

4. 另一个指针newhead一直指向新开辟的空间，用来记住头节点

5. 用哨兵位先指向头节点

6. slow指向头节点，fast指向第二个节点，guard指向哨兵位，newhead一直指向哨兵位。
   

7. 比较slow和fast,不同都进一，相同，fast进一

8. 最后slow与fast不同的时候，guard要连向fast，slow要指向fast,fast再进一

注意：

1.先判断pHead是否为空
2.fast一直进一，走动NULL的情况

如图：

代码如下：

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;
    }
};

总结

希望你们有自己的收获，谢谢点赞