1. 请编写一个算法，删除单链表中值相同的多余结点，使得最后得到的链表中的所有结点的数据域值都不同。

Question

并分析你的算法的复杂性。

Answer 1

第一总算法
设两个指针p,q
p<-head
repeat
{
q<-p.next
repeat
{
if (p.data=q.data) { k<-q.next;del(q);q<-k;}
else q<-q.next
}until q=nul
p<-p.next
}until (p=null) or (p.next=null)
时间为O(n*n) 空间O(1)
还有一种算法
设一个指针p
数组 hash[1..maxnumber] as type byte
p<-head
repeat
{
if (hash[p.data]=1 ) { k<-p.next;del(p);p<-k;} else {hash[p.data]<-1; p<-p.next}
}until p=null
时间为O(n) 空间O(m)