1 ）算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行 一趟扫描。 因为 |data| ≤n，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同 时检查 q[|data|]的值，如果为 0，则保留该结点，并令 q[|data|]=1；否则，将该结点从链表中删除。
typedef struct node{ int data; struct node *link; }NODE; typedef NODE *PNODE; void func (PNODE h,int n){ PNODE p=h,r; int *q,m; q=(int *)malloc(sizeof(int)*(n+1));//申请n+1个位置的辅助空间 for(int i=0;i<n+1;i++) //数组元素初值置为0 *(q+i)=0; while(p->link!=NULL) { m=p->link->data>0?p->link->data:-p->link->data; if(*(q+m)==0) //判断该结点的data是否已出现过 { *(q+m)=1; //首次出现 p=p->link; //保留 } else{ //重复出现 r=p->link; //删除 p->link=r->link; free(r); } } free(q); }
算法的时间复杂度为 O(m) ，空间复杂度为 O(n) 。
