leetcode 82.删除链表中的重复元素II,我的消去重复元素部分的函数是有错吗,为什么相同的数消不去呢?

作者站长头像
站长
· 阅读数 7

leetcode 82.删除链表中的重复元素II,我的消去重复元素部分的函数是有错吗,为什么相同的数消不去呢?这是我的代码实现:

typedef struct Node {
    int val;
    struct Node* next;
}Node, * ListNode;
ListNode LinkListInit();
bool createTail(ListNode L);
void printLinkList(ListNode L);
int getLen(ListNode L);

//初始化链表
ListNode LinkListInit() {
    Node* L;
    L = (Node*)malloc(sizeof(Node));   //申请结点空间 
    if (L == NULL) { //判断是否有足够的内存空间 
        printf("申请内存空间失败\n");
    }
    L->next = NULL;//将next设置为NULL,初始长度为0的单链表 
    return L;
}

//移除链表中元素
ListNode removeElements(ListNode L, int val) {
    ListNode p = NULL, q, R;
    ListNode prev = NULL;
    R = LinkListInit();
    p = L;
    if (p == NULL) {
        return NULL;
    }
    while (p) {
        if (p->val == val && p->next != NULL) {
            q = p->next;
            p->val = p->next->val;
            p->next = q->next;
            free(q);
        }
        else if (prev != NULL && p->val == val && p->next == NULL) {
            prev->next = NULL;
            free(p);
            p = NULL;
        }
        else {
            prev = p;
            p = p->next;
        }
    }
    if(L->val == val){
        return NULL;
    }else{
        return L;
    }
}

//删除链表中的元素
ListNode deleteDuplicates(ListNode L) {
    ListNode p, q,n;
    Node *prev;
    ListNode P;
    int flag = 0;
    int temp = 0;
    P = LinkListInit();
    p = L;
    if (p == NULL) {
        return NULL;
    }
    if(p != NULL && p->next != NULL && p->next->next == NULL && p->val == p->next->val){
        return NULL;
    }
    while (p) {
        prev = p;
        q = p->next;
        if (q != NULL && prev->val == q->val) {
            temp = prev->val;
            //printf("123\n");
            printLinkList(p);
            removeElements(p, prev->val);
            printLinkList(p);
        }
        else {
            p = p->next;
        }
    }
    //printLinkList(L);
    if(temp != 0){
        removeElements(L,temp);
    }
    return L;
}

//输出链表
void printLinkList(ListNode L)
{
    ListNode p;
    p = LinkListInit();
    if (L == NULL) {
        printf("L为空\n");
    }
    else {
        p = L;
    }
    if (p == NULL) {
        printf("null");
    }
    while (p)
    {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}

我的思路是这样的,首先写一个函数(removeElements)来移除链表中的指定元素,之后实现目标函数(deleteDuplicates),对链表进行循环,当遇到值相同的元素时,执行removeElements函数对相同的元素进行删除操作。leetcode 82.删除链表中的重复元素II,我的消去重复元素部分的函数是有错吗,为什么相同的数消不去呢?是我的removeElements函数有问题吗,为什么最后的1死活无法消去?

回复
1个回答
avatar
test
2024-07-01

算法同学,这么晚还在刷算法,真卷!加油 我在vc里复制了你的代码,跑了一下,发现你的removeElements函数有一处问题,导致最后的1无法被删除。在removeElements函数中,当p->val == val且p->next == NULL时,你将prev->next设置为NULL,但没有更新L的值(值的传递问题)。因此,即使你删除了最后一个元素,L仍然指向原来的链表,而不是NULL。所以,在deleteDuplicates函数中,temp不为0时,你需要将L的值更新为removeElements函数的返回值。修改removeElements函数的最后一部分如下:

if (L->val == val) {
    L = L->next;
    return L;
}
else {
    return L;
}

链表对于以后的开发非常重要,leetcode也有好几个和它有关的专门的付费专题章节(坦白的说我还没买),包含刷题和视频,印象里官方标记难度为mid,部分偏hard,内容应该也不错,可以买来多看看(我不是广告)。

回复
likes
适合作为回答的
  • 经过验证的有效解决办法
  • 自己的经验指引,对解决问题有帮助
  • 遵循 Markdown 语法排版,代码语义正确
不该作为回答的
  • 询问内容细节或回复楼层
  • 与题目无关的内容
  • “赞”“顶”“同问”“看手册”“解决了没”等毫无意义的内容