首页 > 试题广场 >

删除有序链表中重复的元素-II

[编程题]删除有序链表中重复的元素-II
  • 热度指数：193212 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为, 返回.
给出的链表为, 返回.

数据范围：链表长度 ，链表中的值满足
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

{1,2,2}

输出

{1}
示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
C
湫湫宁头像 湫湫宁 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* create(int value)
{
    struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
    new->val = value;
    new->next = NULL;
    return new;
}
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    struct ListNode* new = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head, *p, *q;
    int a = 0;

    if(cur == NULL || cur->next == NULL)
    {
        return head;
    }
    new->val = cur->val;
    new->next = NULL;
    q = new;
    while(cur != NULL && cur->next != NULL)
    {
        if(cur->val == cur->next->val)
        {
            p = cur->next;
            cur->next = NULL;
            cur = p;
            a = 1;
        }
        else 
        {
            if(a == 0)
            {
                q->next = create(cur->val);
                q = q->next;
            }
            cur = cur->next;
            a = 0;
        }
    }
    if(a == 0)
    {
        q->next = cur;
    }
    return new->next;
}
针对上题的解法，加入一个状态量用于判决，若是存在相同的值便不存入新链表中
发表于 2024-08-16 10:32:57 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    struct ListNode *res, *p;
    bool DelectFlag = false;
    if(head==NULL || head->next==NULL)
        return head;

    p=head->next;
    while(p!=NULL) {
        if(p->val == head->val) {
            DelectFlag = true;
            break;
        }
        p = p->next;
    }

    res = deleteDuplicates(head->next);
    if(DelectFlag) {
        p = res;
        if(p==NULL)
            return p;
        if(p->val == head->val) 
            return p->next;
        while(p->next!=NULL) {
            if(p->next->val == head->val) {
                p->next = p->next->next;
                return res;
            }
            p = p->next;
        }
        return res;
    }
        
    head->next = res;
    return head;
}

发表于 2024-03-16 00:27:54 回复(0)
C
戏子多秋m头像 戏子多秋m

为什么不行大佬们，好不容易有一题有思路，但是还是错的 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
 #include <stdio.h>
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    struct ListNode *pTemp =head;
    struct ListNode *list;//删除重复后的列表存在这里
    struct ListNode listhead;//链表头
    listhead.next=list;
    int flag=0;//标志位，看看有没有犯罪记录
    while(pTemp)
    {
        if(pTemp->val==(pTemp->next)->val)//如果有相等
        {
            flag=1;//就记录犯罪记录
        }
        else{
            //这里判断一下是否有前科
            if(flag)//如果有前科
            {
                 list=pTemp->next;//就跳过它
                 flag=0;//并且消除一下犯罪记录
            }
            else//如果没前科
            {
               // flag=0;
                list=pTemp;//将它保存下来
            }
            list=list->next;
       }
        pTemp=pTemp->next;
    }
   // printf("%d",flag);
    if(flag)
    {
        return NULL;
    }
    return listhead.next;
}


发表于 2024-03-04 21:00:34 回复(0)
C
干饭睡大觉头像 干饭睡大觉 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
#include <stdlib.h>
int option=0;
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    struct ListNode* headnode=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* first,*last,*temp=headnode;
    headnode->next=head;
    if(!head)
        return NULL;
    while(temp)
    {
        if(!(temp->next&&temp->next->next))
        break;
        first=temp->next;
        last=first->next;
        while(first->val==last->val)
        {
            option=1;
            last=last->next;
            if(!last)
            break;
        }
        if(option==1)
        {
            temp->next=last;
            option=0;
        }
        else
        temp=temp->next;
    }
    return headnode->next;
}

编辑于 2024-02-05 10:52:19 回复(0)
C
牛客360738433号头像 牛客360738433号
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // write code here
    typedef struct ListNode ListNode;
    ListNode* pre = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pre_pre = (ListNode*)malloc(sizeof(ListNode));
    ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
    pre_pre = NULL;
    pre = head;
    cur = head->next;
    while (cur) {
        if (pre->val < cur->val) {
            pre_pre = pre;
            pre = cur;
            if (cur->next != NULL)
                cur = cur ->next;
            else {
                return head;
            }
        } else {
            if (head == pre) {
                while (pre->val == cur->val) {
                    if (cur->next != NULL)
                        cur = cur->next;
                    else {
                        return NULL;
                    }
                }
                head = cur;
                pre = head;
                if (cur->next != NULL)
                    cur = cur ->next;
                else {
                    return head;
                }
            } else {
                while (pre->val == cur->val) {
                    if (cur->next != NULL)
                        cur = cur->next;
                    else {
                        pre_pre->next=NULL;
                        return head;
                    }
                }
                pre_pre->next = cur;
                pre = cur;
                if(cur->next!=NULL){
                    cur = cur -> next;
                }
                else{
                    return head;
                }
            }
        }
    }
    return head;
}
发表于 2023-07-24 02:01:25 回复(0)
C
吾辈长歌头像 吾辈长歌
能想到的最精简的代码了 
struct ListNode* deleteDuplicates(struct ListNode* head ) 
{
    if(head==NULL || head->next==NULL)
        return head;

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *q = dummy;
    struct ListNode *p = dummy;

    while(p!=NULL)
    {
        if(p->next!=NULL && p->val==p->next->val)
        {
            p = p->next;
            continue;
        }
        p = p->next;
        if(p!=NULL && p->next!=NULL && p->val==p->next->val)
        {
            p = p->next;
            continue;
        }
        q->next = p;
        q = q->next;
    }

    return dummy->next;
}

发表于 2023-04-15 18:19:55 回复(0)
C
帅奶哟。头像 帅奶哟。 
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    //head为空或只有一个元素时，直接返回head
    if (head == NULL || head->next == NULL) return head;

    int s[2001] = {0};
    int count = 0;  //记录单个出现元素个数
    int i;

    struct ListNode *p = head;
    struct ListNode *cur = head;

    //s数组记录出现元素的次数
    while (p) {
        s[p->val+1000]++;
        p = p->next;
    }
    
    //计算单个出现元素个数
    for (i = 0; i < 2001; i++){
        if (s[i] == 1) count++;
    }
    //若没有只出现一次的元素则返回NULL
    if (count == 0) return NULL;

    //只将出现一次的元素下标+1000赋值给p->val
    p = head;
    for (i = 0; i < 2001; i++){
        if (s[i] == 1) {
            p->val = i-1000;
            cur = p;
            p = p->next;
        }
    }
    //最后一个元素指向NULL；
    cur->next = NULL;
    return head;
}

发表于 2023-03-20 14:53:32 回复(0)
C
会飞的芜香蛋头像 会飞的芜香蛋
三指针顺序遍历 
struct ListNode* deleteDuplicates(struct ListNode* head){
    if(!head || !head->next)//链表为空或只有一个节点
        return head;

    struct ListNode* per = NULL;
    struct ListNode* p = head;
    struct ListNode* q = head->next;
    if(p->val == q->val){//找第一个不重复的节点
        while(q && p->val == q->val){
            while(q && p->val == q->val){
                p = p->next;
                q = q->next;
            }
            p = p->next;
            if(q)
                q = q->next;
        }
        if(!q)//遍历到表尾
            return p;
    }

    head = p;//第一个不重复的节点
    per = p;
    p = q;
    q = q->next;

    while(q){//删除剩下重复的节点
        while(q && p->val == q->val){
            while(q && p->val == q->val){
                p = p->next;
                q = q->next;
            }
            p->next = NULL;
            p = q;
            if(q)
                q = q->next;
            per->next = p;
        }
        if(q){
            per = p;
            p = q;
            q = q->next;
        }
        else{
            return head;
        }
    }

    return head;
}


发表于 2023-02-09 17:10:10 回复(0)
C
lijd头像 lijd 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here

    if(head == NULL || head->next == NULL){
        return head;
    }

    // ptr3指向返回链表的最后一个元素
    struct ListNode* ptr1 = head, *ptr2 = ptr1->next, *ptr3 = NULL;
    head = NULL;
    int pre_val = 1001;

    while(ptr1)
    {
        if(ptr2) {
            if(ptr1->val == ptr2->val) {
                pre_val = ptr1->val;

                ptr1 = ptr2->next;
                if(ptr1 != NULL)
                    ptr2 = ptr1->next;
                    
                if(head != NULL) {
                    ptr3->next = ptr1;
                }
                
                continue;
            }else{
                if(ptr1->val == pre_val) {
                    ptr1 = ptr2;
                    ptr2 = ptr2->next;
                    if(head != NULL) {
                        ptr3->next = ptr1;
                    }
                    continue;
                }else{
                    if(head == NULL) {
                        head = ptr1;
                    }
                    ptr3 = ptr1;

                    ptr1 = ptr2;
                    ptr2 = ptr2->next;
                }
            }
        }else{
            if(ptr1->val == pre_val) {
                if(head) {
                    ptr3->next = NULL;
                }
            }else{
                if(head){
                    ptr3->next = ptr1;
                }else{
                    head = ptr1;
                }
            }
            break;
        }
    }

    return head;
}

发表于 2023-01-13 09:21:16 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplicates(struct ListNode* head ) 
{
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode *p = head,*q = head,*prev = NULL;
    int num;
    while(p && p->next)
    {
        if(p->val == p->next->val)
        {
            num = p->val;
            while(p->val == num)
            {
                if(prev == NULL)
                {
                    q = p->next;
                    p->next = NULL;
                    p = q;
                }
                else
                {
                    prev->next = p->next;
                    p->next = NULL;
                    p = prev->next;
                }
                if(p == NULL)
                {
                    return q;
                }
            }
            continue;
        }
        prev = p;
        p = p->next;
    }
    return q;
}

发表于 2022-11-02 21:09:15 回复(0)
C
冬xur头像 冬xur 
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head==0)    return 0;
    
    //不为空结点
    struct ListNode* np=(struct ListNode*)malloc(sizeof(struct ListNode));
    np->next=head;
    
    struct ListNode* p0=np;struct ListNode* p1=head;
    int count=0;
    while(p1!=0){
        count=0;
        while(p0->next->val==p1->val&&p1!=0){
            p1=p1->next;count++;
        }
        if(count==1)    p0=p0->next;
        p0->next=p1;
    }
    return np->next;
}

发表于 2022-08-21 20:24:29 回复(0)
C
菜团子鼠鼠头像 菜团子鼠鼠 
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL)//链表为空或者只有一个，直接返回
    {
        return head;
    }
    struct ListNode*h = NULL;//创建一个新单链表，这是头节点
    struct ListNode*t = NULL;//尾结点
    struct ListNode*pnew = NULL;//新结点
    struct ListNode*p = head;
    while(p)
     {
        if(p->next!=NULL && p->val == p->next->val)
        {
            while(p->next != NULL && p->val == p->next->val)//用while找到所有相同的数
            {
                p = p->next;
            }
           p = p->next；//往下走一步，所有相同的都没有获取
        } 
        else if(p->val != p->next->val)//获取不同的数
        {
             struct ListNode* pnew = malloc (sizeof(struct ListNode));
             pnew->val = p->val;
             pnew->next = NULL;
            if(h == NULL)//从无到有
            {
               h = pnew;
               t = pnew;
            }
            else//尾插
            {
                t->next = pnew;
                t = pnew;
            }
             p = p->next;
         }
    }
    return h;
}

发表于 2022-07-23 13:58:37 回复(0)
C
风神3333头像 风神3333 
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(!head)
        return NULL;
    struct ListNode* old = head;
    struct ListNode* new = head->next;
    struct ListNode* headtemp = (struct ListNode*)malloc(sizeof(struct ListNode));
    headtemp->val = 9999;
    headtemp->next = head;
    struct ListNode* prv = headtemp;
    
    int same_flag = 0;
    while(new){
        if(old->val == new->val){
            same_flag = 1;
            new = new->next;
        }
        else{
            if(same_flag){
                same_flag = 0;
                prv->next = new;
                old = new;
                new = new->next;
            }
            else{
                new = new->next;
                old = old->next;
                prv = prv->next;
            }
        }
    }
    if(same_flag)
        prv->next = new;
    return headtemp->next;
}

发表于 2022-07-20 17:36:31 回复(0)
C
阿金要努力头像 阿金要努力 
struct ListNode* deleteDuplicates(struct ListNode* head)
{
    if(head==NULL)
        return head;
    struct ListNode* preHead=(struct ListNode*)malloc(sizeof(struct ListNode));
    preHead->next=head;
    struct ListNode* pre=preHead;
    struct ListNode* tail=head;
    while(tail)
    {
        while(tail->next&&tail->val==tail->next->val)
        {
            tail=tail->next;
        }
        if(pre->next==tail)
            pre=pre->next;
        else
            pre->next=tail->next;
        tail=tail->next;
    }
    return preHead->next;
}

发表于 2022-05-27 17:42:18 回复(2)
C
牛客780307272号头像 牛客780307272号
我的思路就是两个指针遍历，一个指针作为头结点，用t记录前一个结点的值，相等就跳过，不等就接上头结点，链表的最后一个元素由于fast到空指针会跳过，循环出来再判别要不要接上。
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head==NULL)
        return head;
    struct ListNode*slow=head,*fast=head->next;
    struct ListNode*p1=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*p2=p1;
    int t=-1001;
    while(fast){
        if(slow->val==fast->val||slow->val==t){
            t=slow->val;
            slow=slow->next;
            fast=fast->next;
        }
        else{
            p1->next=slow;
            p1=p1->next;
            slow=slow->next;
            fast=fast->next;
            t=p1->val;
        }
    }
    if(slow->val!=t){
        p1->next=slow;
        p1=p1->next;
    }
    p1->next=NULL;
    return p2->next;   
}
发表于 2022-05-24 20:16:40 回复(0)
C
已注销头像 已注销 
void del_sameval_node(struct ListNode **head, struct ListNode **bef_prev, struct ListNode **prev, struct ListNode **cur, struct ListNode **del_node);

struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    struct ListNode *prev, *cur, *del_node = NULL, *bef_prev = NULL;
    unsigned char flag = 0;
    
    if (head == NULL || head->next == NULL) {
        return head;
    }
    prev = head;
    cur = head->next;
    while (cur != NULL) {
        if (prev->val != cur->val && flag == 0) {
            bef_prev = prev;
            prev = cur;
            cur = cur->next;
        } else if (prev->val == cur->val && flag == 0) {
            cur = cur->next;
            flag = 1;
        } else if (prev->val == cur->val && flag == 1) {
            cur = cur->next;
        } else if (prev->val != cur->val && flag == 1) {
            del_sameval_node(&head, &bef_prev, &prev, &cur, &del_node);
            flag = 0;
        }
    }
    if (flag) {
        del_sameval_node(&head, &bef_prev, &prev, &cur, &del_node);
    }
    
    return head;
}

void del_sameval_node(struct ListNode **head, struct ListNode **bef_prev, struct ListNode **prev, struct ListNode **cur, struct ListNode **del_node) {
    if (*head == *prev) {
        *head = *cur;
    } else {
        (*bef_prev)->next = *cur;
    }
    *del_node = *prev;
    while (*prev != *cur) {
        *prev = (*prev)->next;
        free(*del_node);
        *del_node = *prev;
    }
    *cur = (*prev != NULL ? (*prev)->next : NULL);
}

发表于 2022-03-24 03:09:09 回复(0)
C
无敌俊俊头像 无敌俊俊
C 语言写的： 

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */

typedef struct ListNode Node;
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    
    Node *pre = NULL;
    Node *mid = head;
    Node *cur = mid->next;
    //开头重复
    if(mid->val == cur->val)
    {
        while(cur && mid->val == cur->val)
        {
            //每次循环释放mid结点
           Node *p3 = mid;
            mid = cur;
            cur = cur->next;
            free(p3);
            if( !cur)
            {
                return NULL;
            }
        }
        //释放cur结点前一个的mid结点
        Node *p4 = mid;
        pre = cur;
        mid = cur->next;
        if(cur->next ==  NULL)
        {
            cur = NULL;
        }
        else
        {
             cur = cur->next->next;
        }
       
        printf("%d ",pre->val);
        head = pre;
        free(p4);
    }
    
    
    
    //中间重复
    while(cur)
    {
        //如果删除后的首结点还重复，继续删除
        while(1)
        {
            //如果头结点和第二个结点重复，则删除，一直删到不重复为止
            if(pre->val == mid->val && pre )
            {
            while(cur && pre->val == mid->val)
            {
                
                Node *p5 = pre;
                pre = mid;
                mid = cur;
                cur = cur->next;
                free(p5);
               
            }
                //各结点后移
               Node *p6 = pre;
               pre = mid;
               mid = cur;
                //如果cur不为空。则cur后移
               if(cur)
               {
                   cur = cur->next;
               }
               free(p6);
               head = pre;
            }
            else
            {
                break;
            }
        }
        //到这一步说明前面的已经没有重复了，只存在中间重复或者末尾重复
        if(mid->val == cur->val && mid != cur)
        {
            Node *p1 = cur;
            cur = cur->next;
            free(p1);
            //结尾重复
            //如果cur为空，直接让pre指向空，并释放mid结点和cur结点
            if(!cur)
            {
                pre->next = NULL;
                free(mid);
                free(cur);
                return head;
            }
            //如果cur的值不等于mid的值并且cur不为空，则cur后移，并同时删除mid结点
            if(cur->val != mid->val && cur)
            {
                Node *p2 = mid;
                mid = cur;
                cur = cur->next;
                free(p2);
            }
           //此时mid结点的值已经不等于cur结点的值，直接让pre结点指向mid结点，让链表连接起来
            pre->next = mid;
            
        }
        else
        {
            //都不相等，直接后移
            pre = mid;
            mid = cur;
            cur = cur->next;
        }
    }
    
    return head;
}


发表于 2022-03-13 19:42:21 回复(0)
提交观点

问题信息

链表
难度：
20条回答 26297浏览

热门推荐

通过挑战的用户

查看代码

相关试题

删除有序链表中重复的元素-II

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号