826. 单链表

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；删除第 k 个插入的数后面的数；在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

H x，表示向链表头插入一个数 x x x 。D k，表示删除第 k k k个插入的数后面的数（当 k k k为 0 时，表示删除头结点）。I k x，表示在第 k k k 个插入的数后面插入一个数 x x x（此操作中 k k k 均大于 0）。

共一行，将整个链表从头到尾输出。

e[i] 表示编号为 i 的点的值。 e[i] = j ，表示单链表中下标是i的点的后继节点的下标为j。ne[i] 表示编号为 i 的点的后继节点的下标。h 表示头节点的编号。idx 存储了当前可以使用的最新的点的下标。

void add(int a,int b,int c){//头插法，每次向头指针的后边插入一个点
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

4
H 10
H 20
H 30
H 40
----------------------------------------------------------------------------
cout< 
输出
3
3 40 2
2 30 1
1 20 0
0 10 -1
 
第 k 个插入的数的 idx 是 k-1。
 
 
向链表头插入一个数 
      
       
        
         
          x
         
        
        
         x
        
       
      x
 
void add(int x){
    e[idx]=x,ne[idx]=h,h=idx++;
}
  
D k，表示删除第 
      
       
        
         
          k
         
        
        
         k
        
       
      k个插入的数后面的数（当 
      
       
        
         
          k
         
        
        
         k
        
       
      k为 0 时，表示删除头结点）。
 
本题有个坑，删除头节点指删除头节点后边的节点，剩余的节点前移。
void remove(int k){
    k--;
    ne[k]=ne[ne[k]];
}
  
I k x，表示在第 
      
       
        
         
          k
         
        
        
         k
        
       
      k 个插入的数后面插入一个数 
      
       
        
         
          x
         
        
        
         x
        
       
      x（此操作中 
      
       
        
         
          k
         
        
        
         k
        
       
      k 均大于 0）。
 
void insert(int k,int x){
    k--;
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
 
 
#include 
#include 
#include 

using namespace std;

const int N = 1e5+10;

int h,ne[N],e[N],idx;
int m;

void add(int x){
    e[idx]=x,ne[idx]=h,h=idx++;
}

void remove(int k){
    k--;
    ne[k]=ne[ne[k]];
}

void insert(int k,int x){
    k--;
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
int main(){
    cin>>m;
    idx=0;
    h=-1;
    while(m--){
        string s;int k,x;
        cin>>s;
        if(s=="H"){
            cin>>x;
            add(x);
        }
        else if(s=="D"){
            cin>>k;
            if(!k){
                h=ne[h];
                // 因为h的下标就是最新插入的节点的下标，所以是一个ne[h]
                // h=ne[ne[h]];
            }
            else
            remove(k);
        }
        else{
            cin>>k>>x;
            insert(k,x);
        }
    }
    for(int i=h;~i;i=ne[i]){
        cout<