题目描述

blablabla

样例

//
//  main.c
//  acwing单链表
//
//  Created by 战泰霖 on 2021/3/7.
//

#include<iostream>
using namespace std;

const int N = 10010;

int head,e[N],ne[N],idx;
//head表示头节点的下标
//e[i]表示节点i的值
//ne[i]表示节点i的next指针是多少
//idx存储当前已经用到了那个点

void init ()//初始化
{
    head = -1;
    idx = 0;


}
//将x插到头节点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;

}
//将x插到下标是k的点后面
void add(int k,int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}
//将坐标是k的后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;

    cin>>m;

    init();

    while(m--)
    {
        int k,x;
        char op;

        cin>>op;

        if(op=='H')
        {
            cin>>x;
            add_to_head(x);
        }
        else if(op == 'D')
        {
            cin>>k;
            if(!k) head = ne[head];
            remove(k-1);
        }
        else
        {
            cin>> k>> x;
            add(k-1,x);
        }





    }

    for(int i = head;i!=-1;i=ne[i])cout << e[i]<<' ';
    cout<< endl;


    return 0;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla