(15分)用单链表保存 m 个整数,结点的结构为 \( \begin{array}{|c|} \hline \texttt{data} \mid \texttt{link} \\ \hline \end{array} \) ,且 |data|≤n ( n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中 data 的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表 head 如下:
则删除结点后的 head 为:
要求:
⑴ 给出算法的基本设计思想。(3分)
⑵ 使用C或C++语言,给出单链表结点的数据类型定义。(2分)
⑶ 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。(8分)
⑷ 说明你所设计算法的时间复杂度和空间复杂度。(2分)
登录后提交答案
暂无评论,来抢沙发