问题 B: DS单链表—删除重复元素
时间限制: 1 Sec 内存限制: 128 MB
提交: 128 解决: 77
[提交][状态][讨论版]
题目描述
给定n个整数，按输入顺序建立单链表，删除其中的重复数字，输出结果链表。（要求不可以构建新结点，不可以定义新链表。在原链表上删除。）
输入
测试次数t
每组测试数据一行：
n（表示有n个整数），后跟n个数字
输出
对每组测试数据，输出删除重复数字后的结果链表表长和每个元素，具体格式见样例。
样例输入
3
10 1 2 3 4 1 2 10 20 30 20
5 1 1 1 1 1
6 20 22 22 22 22 20
样例输出
7: 1 2 3 4 10 20 30
1: 1
2: 20 22
]
#include<iostream> using namespace std; class ListNode { int data; ListNode *next; friend class linklist; }; class linklist { int len; ListNode *head; public: linklist() { len = 0; head = new ListNode(); } ~linklist() { delete head; } ListNode *index(int i) { if (i<0 || i>len) return NULL; ListNode *p = head; for (int j = 0; j < i; j++) { p = p->next; } return p; } int insert(int i, int item) { if (i<0 || i>len + 1) return -1; ListNode *p = index(i - 1); ListNode *s = new ListNode(); s->data = item; p->next = s; p = p->next; len++; } /*void insert( int item) { ListNode *p = head; ListNode *s = new ListNode(); s->data = item; p->next = s; p = p->next; len++; }*/ void del() { ListNode *p = head; ListNode *q = new ListNode(); ListNode *m = new ListNode(); ListNode *s = new ListNode(); for (int i = 0; p != NULL; i++) { p = p->next; if (p == NULL) break; int x = p->data; m = p; for (int j = i + 1; q!=NULL; j++) { ListNode *q = new ListNode(); q = m->next; if (q == NULL) break; if (x == q->data){ m->next = q->next; delete q; len--; } else { m = m->next; } } } } int getlen() { return len; } void show() { ListNode *p; p = head->next; while (p != NULL) { cout << " " << p->data; p = p->next; } cout << endl; } }; int main() { int t; cin >> t; while (t--) { linklist list; int n, num; cin >> n; for (int i = 1; i <= n; i++) { cin >> num; list.insert(i, num); } //list.show(); list.del(); cout << list.getlen() << ":"; list.show(); } return 0; }
