Question

0 0

去除有序列表中的重复元素

给定一个 有序 链表，去除其中重复的元素,让每个重复的元素只显示一次，我是用单指针做的，但是很奇怪当输入为｛1，1，....｝这种头部元素重复的情况下不能去重，其它情况没有问题，我知道是头部元素没处理好，但到底是哪一行代码逻辑不对呢？代码如下：


 struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        ListNode **pcur=&head;
        if(head==NULL||head->next==NULL){
        return head;
        }
        while((*pcur)->next!=NULL)
        {
            if((*pcur)->val==(*pcur)->next->val)
            {
                *pcur=(*pcur)->next;

            }
            else
            {
                pcur=&((*pcur)->next);

            }
        }
        return head;
    }
};

c 数据结构算法 C++

10 years, 2 months ago

almosty

share

almosty 10 years, 2 months ago

Answer 1

0

2014-10-27 09:13:00更新

你仔细研究一下我写的 testAsignPoint 和 testAsignPointAgain 函数就会明白为什么你的二级指针无效了。

还是那句话，你要记住，指针就是一个变量，存的是32位数据，记住这个才能真正的理解指针。

另外 @pezy 说有内存漏洞，实际上我的完整代码是下面的，我大学是acm出身的，只有初期才使用真正的指针，后期acm中都是使用数组代表指针的，这才是真正的升华，同样存的是地址，这时只不过地址是数组的下标罢了。

当然，下面的代码我没有使用数组代替指针，不然就没法用指针来讲了。

最后，我加上我的测试的完整代码：


 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<queue>
#include<map>
#include<cmath>
#include<stack>
#include<algorithm>
#include<functional>
#include<stdarg.h>
using namespace std;
#ifdef __int64
typedef __int64 LL;
#else
typedef long long LL;
#endif

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    ListNode():next(NULL) {}
} str[100];
ListNode *deleteDuplicates(ListNode *head) {
    while(head && head->next) {
        if(head->val==head->next->val) {
            head->next = head->next->next;
        } else {
            head = head->next;
        }
    }
    return head;
}

ListNode *oldDeleteDuplicates(ListNode *head) {
    ListNode **pcur=&head; //取得 head 变量的
    if(head==NULL||head->next==NULL) {//特判是不是没有元素或者只有一个元素
        return head;
    }
    /*
    这个时候 head 是 one 的地址。
    pcur 是 head 的地址。
    *pcur 就代表 head 了，即 one

    (*pcur)->nex 指向 two,所以不结束循环，且比较相等了
    所以你给 *pcur 赋值，也就是给 head 赋值。
    此时 *pcur 就指向  two 了。

    */
    while((*pcur)->next!=NULL) {
        if((*pcur)->val==(*pcur)->next->val) {
            *pcur=(*pcur)->next;
            // (*pcur)->next =((*pcur)->next->next);
        } else {
            pcur=&((*pcur)->next);

        }
    }
    return head;
}

void testAsignPoint(ListNode *head) {
    printf("    asign begin=%0x\n",head);
    head = head->next;
    printf("    asign begin=%0x\n",head);
}

void myprintf(ListNode* head) {
    while(head != NULL) {
        printf("%d ", head->val);
        head=head->next;
    }
    printf("\n");
}

void testAsignPointAgain(unsigned int addr){
    printf("    asign begin=%0x\n",addr);
    addr = (unsigned int)((ListNode *)addr)->next;//28fef8
    printf("    asign begin=%0x\n",addr);
}

void test(ListNode* ptest) {


    printf("ptest begin=%0x\n",ptest);//28fef0
    testAsignPoint(ptest);
    printf("one ptest =%0x\n",ptest);//28fef0
    printf("same as before code");
    testAsignPointAgain((unsigned int)(ptest));
    printf("one ptest =%0x\n",ptest);//28fef0

    printf("ptest=%0x\n",ptest);
    myprintf(ptest);
    oldDeleteDuplicates(ptest);
    myprintf(ptest);
    deleteDuplicates(ptest);
    printf("ptest=%0x\n",ptest);
    myprintf(ptest);
}

void testSample(){
    ListNode three(1, NULL);
    ListNode two(0, &three);
    ListNode one(0, &two);
    test(&one);

}

int main() {
    int n = 10;
    for(int i=0; i<n; i++) {
        str[i].val = i/2;
        str[i].next = &str[i+1];
    }
    str[n].val = n/2;
    str[n].next = NULL;
    printf("deleteDuplicates begin\n");
    myprintf(str);
    deleteDuplicates(&str[0]);
    myprintf(str);
    printf("deleteDuplicates end\n");
    printf("\n");
    printf("test Asign Point begin\n");
    testSample();
    printf("test Asign Point begin\n");

    return 0;
}

分割线

更新时间：2014-10-26 15:28

先告诉你我对指针的定义:指针可以理解为一个类型，或者一类类型。和int,double,自定义类型等是没有区别的。

实际上最简洁的代码是下面的样子


 ListNode *deleteDuplicates(ListNode *head) {
    while(head && head->next) {
        if(head->val==head->next->val) {
            head->next = head->next->next;
        } else {
            head = head->next;
        }
    }
    return head;
}

之所以你使用错误，根本原因是由于你错误的理解了指针：以指针为参数，只会修改指针的值，如果对指针变量修改，原来那个指针是不受影响的。

前端时间刚好我看了一本书《重构~改善既有代码的设计》,里面的一个重构目标就是对于串的指针全部改成 final, java 中没有指针，但是传的对象全部是引用，如果添加为 final 就是不能给变量赋值，但是可以修改对象里面的值。c 语言的 const 也有这个漏洞，算是hack做法吧，不推荐。

扯远了，回头来看你的问题，不理解的时候最简单的方法就是自己模拟一下。

假设有链表有三个元素


 ListNode three(1, NULL);
    ListNode two(0, &three);
    ListNode one(0, &two);

结构是这个样子：one -> two -> three

为了传入指针，我们事先一个函数吧。


 void test(ListNode* pTest){
    printf("head=%0x\n",pTest);
    deleteDuplicates(pTest);
   printf("head=%0x\n",pTest);
}

test(&one);

对于这个 pTest以参数形式传给deleteDuplicates，由于不是引用，所以传进去的是一个32位数据，可以称为地址。

接下来我们模拟一下你的函数：


 ListNode *oldDeleteDuplicates(ListNode *head) {
    ListNode **pcur=&head; //取得 head 变量的
    if(head==NULL||head->next==NULL) {//特判是不是没有元素或者只有一个元素
        return head;
    }
    /*
    这个时候 head 和 pTest 的值一样，都是 one 的地址。
    pcur 是 head 的地址。
    *pcur 就代表 head 了，即 one

    (*pcur)->next 指向 two,所以不结束循环，且比较相等了
    所以你给 *pcur 赋值，也就是给 head 赋值。
    此时 *pcur 就指向  two 了。

    而此时 pTest 还是指向 one 的，而one还是指向two的。

    模拟至此，下面再看看为什么是这个样子。
    */
    while((*pcur)->next!=NULL) {
        if((*pcur)->val==(*pcur)->next->val) {
           *pcur=(*pcur)->next;
           // (*pcur)->next =((*pcur)->next->next);
        } else {
            pcur=&((*pcur)->next);

        }
    }
    return head;
}

为什么 pTest 没有改变呢？

我们再测试一下。


 void testAsignPoint(ListNode *head) {
    printf("    asign begin=%0x\n",head);
    head = head->next;
    printf("    asign begin=%0x\n",head);
}

void test(ListNode* ptest) {
    printf("test begin=%0x\n",ptest);
    testAsignPoint(ptest);
    printf("test end =%0x\n",ptest);
}

test(&one);

输出时下面的数据


 test begin=28fef0
    asign begin=28fef0
    asign begin=28fef8
test end =28fef0

ptest 的地址是不会改变的，因为你传的是 ptest 的值，而不是 ptest 的地址。

分割线

原始回答：

根据你的算法： *pcur=(*pcur)->next; 得到一个结论： 当重复时，你删除的是前一个

但是如果头部重复的时候，你只是改变一下指针，这样的算法肯定不能解决头部问题的。

你需要改变算法为：当重复的时候，删除后一个。

即使后面的你一定要使用你的那个算法，那头部就只有特判然后使用 重复时删除 后面的算法

删除后一个的算法如下：


 ListNode *deleteDuplicates(ListNode *head) {
    ListNode **pcur=&head;
    if(head==NULL||head->next==NULL) {
        return head;
    }
    while((*pcur)->next!=NULL) {
        if((*pcur)->val==(*pcur)->next->val) {
           // *pcur=(*pcur)->next;
            (*pcur)->next =((*pcur)->next->next);
        } else {
            pcur=&((*pcur)->next);

        }
    }
    return head;
}

answered 10 years, 2 months ago

有病的小鸡肉

share

有病的小鸡肉 answered 10 years, 2 months ago

去除有序列表中的重复元素

almosty

Answers

分割线

分割线

有病的小鸡肉

Your Answer