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

前言

???路还长

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

题目描述

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

测试样例1:

测试样例2:

测试样例3:

题目思路

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

注意：

如图：

代码如下：

class Solution {
    
public:/*** * @param head ListNode类 * @return ListNode类*/ListNode* deleteDuplicates(ListNode* head) {
    // write code hereif(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：

测试样例2：

题目思路

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再进一

注意：

如图：

代码如下：

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

总结

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