题目描述

已知线性表中的元素以递增序列排列，并以单链表作存储结构。设计算法删除表中所有值相同的多余元素（使得操作后的线性表中所有的值均不相同），同时释放被删结点空间，并分析算法的时间复杂度。

输入

第一行输入一个正整数n，表示元素个数，n<=100。
第二行输入n个正整数元素，保证元素以递增排列，元素的值<=100。

输出

输出删除相同元素后的链表。

样例输入

5
1 1 3 4 4

样例输出

1 3 4

代码：

#include<bits/stdc++.h>
using namespace std;
typedef struct LNode{int data;struct LNode *next;LNode(int data):data(data),next(NULL){};
}LNode,*LinkList;LinkList CreateLinkList(int n){//创建单链表 LinkList L = (LNode *)malloc(sizeof(LNode));//创建头结点int val;LNode *p;//接收新结点 LNode *tail = L;//尾指针，指向链表的最后一个结点while(n--){scanf("%d",&val);p = (LNode *)malloc(sizeof(LNode));p->data = val;tail->next = p;tail = tail->next;p=p->next;}tail->next=NULL;return L;
}
/*LinkList CreateLinkList(int n){LinkList L = new LNode(-1);//创建头结点LNode *tail=L;int val;while(n--){//	int val;scanf("%d",&val);LNode *p = new LNode(val);tail->next = p;tail = tail->next;} tail->next = NULL;return L;
} */
LinkList Delete_Duplicate(LinkList L,int &len){if(L->next==NULL)return NULL;///如果输入结点为空 LNode *pre = L;//定义一个指针指向头结点的下一个结点LNode *p = L->next;while(p!=NULL){if(pre->data == p->data){pre->next =p->next;free(p);p=pre->next;len--;}else{pre = p;p=p->next;}}return L;}
int main(void){int n;scanf("%d",&n);int len = n;LinkList L = CreateLinkList(len);LNode *p=L->next;LinkList A = Delete_Duplicate(L->next,len);LNode *x = A->next;for(int i=0;i<len;++i){printf("%d ",A->data);A=A->next;}return 0;
}