题目描述

给定N个整数，将这些整数中与M相等的删除
假定给出的整数序列为：1,3,3,0,-3,5,6,8,3,10,22,-1,3,5,11,20,100,3,9,3
应该将其放在一个链表中，链表长度为20
要删除的数是3，删除以后，链表中只剩14个元素：1 0 -3 5 6 8 10 22 -1 5 11 20 100 9
要求：必须使用链表，不允许使用数组,也不允许不删除元素直接输出
程序中必须有链表的相关操作：建立链表，删除元素，输出删除后链表中元素，释放链表
不符合要求的程序即使通过，也会算作0分

样例

  1. 20
  2. 1 3 3 0 -3 5 6 8 3 10 22 -1 3 5 11 20 100 3 9 3
  3. 3

算法

用数组模拟链表， h 表示头结点，t表示尾节点，e[N]表示编号， ne[N]表示后继节点的数组下标，idx表示当前用到的数组下表

(暴力枚举) $O(n^2)$

C++ 代码

  1. #include <iostream>
  3. using namespace std;
  5. const int N = 200010;
  7. int h = -1,t, e[N], ne[N], idx;
  8. int n;
  9. int target;
  11. void add_to_head(int x){
  12.     e[idx] = x;
  13.     ne[idx] = h;
  14.     h = idx ++;
  15.     t = h;
  16. }
  18. void add_to_tail(int x){
  19.     e[idx] = x;
  20.     ne[t] = idx ++;
  21.     t = ne[t];
  22.     ne[t] = -1;
  23. }
  26. int main(){
  27.     cin >> n;
  28.     int x;
  29.     cin >> x;
  30.     add_to_head(x);
  31.     n --;
  32.     while(n --){
  33.         cin >> x;
  34.         add_to_tail(x);
  35.     }
  36.     cin >> target;
  38.     while(e[h] == target) h = ne[h];
  40.     int cur = h;
  41.     while(cur != -1 && ne[cur] != -1){
  42.         while(e[ne[cur]] == target) ne[cur] = ne[ne[cur]];
  43.         cur = ne[cur];
  44.     }
  46.     for(int i = h; i != -1; i = ne[i]) cout << e[i] << " ";
  47.     return 0;
  48. }