数据结构实验之链表七：单链表中重复元素的删除

数据结构实验之链表七：单链表中重复元素的删除

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。

Input

第一行输入元素个数 n (1 <= n <= 15)； 第二行输入 n 个整数，保证在 int 范围内。

Output

第一行输出初始链表元素个数； 第二行输出按照逆位序所建立的初始链表； 第三行输出删除重复元素后的单链表元素个数； 第四行输出删除重复元素后的单链表。

Sample Input

10 21 30 14 55 32 63 11 30 55 30

Sample Output

10 30 55 30 11 63 32 55 14 30 21 7 30 55 11 63 32 14 21

Hint

Source

不得使用数组！

涉及到链表重复元素删除问题，首先要考虑应该用到几个游动指针来进行重复元素的删除。首先要有一个游动指针将链表中结点的数据都进行读取一遍（设为P指针），其次应该需要另外两个游动指针来进行重复的结点的删除（分别设为q指针和W指针，q=w->next），当后面的游动结点的数据等于第一个游动指针所指的结点的数据时进行删除操作（即w->data==p->data)，具体就是将q指针的下一个指向w的下一个（q->next=w->next)这里的w指针千万不要进行等于空指针操作，即千万不要

w->next=NULL，因为这样操作之后会使游动指针w的通路丢失，因为前面是w->data=p->data,w是要删除的结点，前面

q->next=w->next此操作已经使w结点的入口打断，如果此时再将w结点的出口打断的话游动指针w就没办法往下进行遍历。所以在将入口打断之后出口不要再管了，不影响的。最后在第一组输出的时候直接逆序建立链表即可。

AC代码：

#include<bits/stdc++.h> using namespace std;//写C的同学改一下头文件即可 typedef struct node { int data; struct node*next; }tree; int main() { struct node*head,*p,*q,*w; head=new tree; // head=(struct node*)malloc(sizeof(struct node));//C语言的结点开辟新空间的语句 head->next=NULL; int n; scanf("%d",&n); for(int i=0;i<n;i++) { p=new tree; // p=(struct node*)malloc(sizeof(struct node)); scanf("%d",&p->data); p->next=head->next; head->next=p; } printf("%d\n",n); p=head->next; while(p) { if(p->next==NULL) { printf("%d\n",p->data); } else { printf("%d ",p->data); } p=p->next; } p=head->next; while(p) { q=p; w=q->next; while(w) { if(w->data==p->data) { n--; q->next=w->next; w=w->next; } else { q=w; w=w->next; } } p=p->next; } printf("%d\n",n); p=head->next; while(p) { if(p->next==NULL) { printf("%d\n",p->data); } else { printf("%d ",p->data); } p=p->next; } return 0; }