来自：年全国硕士研究生入学统一考试综合应用题部分
题目：
用单链表保存m个整数，节点的结构为(data,link)，且
data
例如若给定的单链表head如下：
删除节点后的head为：
要求
(1)给出算法的基本思想
(2)使用c或c++语言，给出单链表节点的数据类型定义。
(3)根据设计思想，采用c或c++语言描述算法，关键之处给出注释。
(4)说明所涉及算法的时间复杂度和空间复杂度。
(1)算法思想：
定义一个大小为N的数组，初始化为0.在遍历链表的同时将数组中索引值为节点的值的绝对值的元素置1.如果此元素已经为1，说明此节点之前已经有与此节点的值的绝对值相等的节点，需将此节点删除。
(2)节点的数据结构定义如下：
typedefstructNode { Intdata; StructNode*next; }Node;
（3）
inta[n];//全局数组标志节点的绝对值的值是否出现过 voidDeleteABSEqualNode(Node*head) { memset(a,0,n);//初始化为0 if(head==NULL) { returnNULL; } Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p-data)]==1)//如果此绝对值已经在节点值的绝对值中出现过 {//则删除当前节点 r-next=p-next; deletep; p=r-next; } else//否则，将数组中对应的元素置1，并将指针指向下一个元素 { a[abs(p-data)]=1; r=p; p=p-next; } } returnhead; }
(4)只遍历一次链表，所以时间复杂度为O(n)，
因为申请大小为n的数组，所以空间复杂度为O(n)，(n为节点绝对值的最大值)。
●编号，输入编号直达本文
●输入m获取文章目录
赞赏