代码在一个递增有序的线性表中,有数值相同的元素存在.若存储方式为单链表,设计算法去

Question

掉数值相同的元素，是表中不在有重复的元素

Answer 1

这是一个简单的单链表操作题。

核心算法：

用两个指针p,pre,其中pre指向p的直接前驱结点。比较p->data和pre->data是否相等，如果相等将p继续只想下一个结点（即：p=p->next），直到不相等为止。此时就要更新pre和p的值，删除pre和p之间的结点(即：pre->next=p;),
接着让p指向pre的下一个结点（即：p=pre->next;），细节上还要注意，输入数据都是一个数的情况，指针p容易指向一个undefined loop(未定义的区域)

复杂度分析：

以lenth=5为例：

最优情况：
输入：1 2 3 4 5
最差情况：
输入：1 1 1 1 1
复杂度：O（n）

附：C++ code

#include
using namespace std;
struct List
{
int data;
struct List * next;
}; //define the Linear List
void creatlist(struct List * &head,int lenth)
{
//creat a List
struct List *p1,*p2;
p1=p2=head;
for(int i=0;i<lenth;i++)
{
p1=(struct List *)malloc(sizeof(struct List));
cin>>p1->data;
p2->next=p1;
p2=p1;
}
p1->next=NULL;
}
void deletesame(struct List *&head)
{
//delete the adjacent elements of same value
struct List *pre=head->next,*p=pre->next;
while(p!=NULL)
{
while(p!=NULL && pre->data==p->data)
p=p->next;
if(p!=NULL) //details! Key to success!
{
pre->next=p;
pre=p;
p=p->next;
}
else pre->next=NULL;
}
}
void display(struct List *&head)
{
//Ouput the List elements
struct List *p=head->next;
while(p!=NULL)
{
cout<data<<" ";
p=p->next;
}
cout<<endl;
}
int main()
{
int lenth;
cout<<"Please enter the lenth of the List:"<<endl;
cin>>lenth;
struct List *head;
head=(struct List *)malloc(sizeof(struct List));
creatlist(head,lenth);
cout<<"Before deleteing:"<<endl;
display(head);
deletesame(head);
cout<<"After deleteing:"<<endl;
display(head);
return 0;
}

Answer 2

void find(node *head){
node *p,q;
p=q=head;
while(p->next!=NULL){
q=p->next;
while(q->data==p->data)
q=q->next; //跳过与p的data相同的节点
p->next=q;//将相同节点删除
p=q;
}
return;
}