算法的核心思想是用空间换时间,使用辅助数组记录链表中已出现的数值 从而只需对链表进行一趟扫描
typedef struct node { int data; struct node* next; }NODE; typedef NODE* PNODE; void func (PNODE h, int n){ //链表中的|data| <= n PNODE p = h, r ; //其中p为工作指针 r为保存删除的结点,以供free掉 int *q; q = (int*) malloc(sizeof(int) * (n+1)); //申请n+1个辅助空间 for(int i=0;i<n+1;i++) q[i] = 0; while(p->next!=NULL){ int temp; temp = p->data >0 ? p->next->data: -(p->next->data); if( q[temp] == 0){ q[temp] = 1; p=p->next; // 移动p指针 } else{ r = p->next; //使得p是r的前驱节点 p->next = r->next; // 对p->next重新赋值既删除了q结点, 又使while循环可以 循环下去 free(r); } } free(q); }