题目描述

用数组模拟单链表
要有疑惑的地方在参考一下这个题解

C++代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int e[N], ne[N], head, idx;

void init(){
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a){
    e[idx] = a;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 在链表k结点后插入一个数a
void insert(int k, int a){
    e[idx] = a;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 删除k结点后的数（注意删除头结点时！！！！）
void remove(int k){
    ne[k] = ne[ne[k]];
}

int main(){
    int m, x, k;
    char ch;
    init();
    cin >> m;
    for(int i = 0; i < m; i++){
        cin >> ch;
        if(ch == 'H'){
            cin >> x;
            insert(x);
        }
        else if(ch == 'D'){
            cin >> k;
            if(k == 0){
                head = ne[head]; // 将头结点删除，需要保证头结点存在
            }
            else
                remove(k - 1);
        }
        else{
            cin >> k >> x;
            insert(k - 1, x);
        }
    }
    for(int i = head; i != -1 ; i = ne[i]){
        cout << e[i] << " ";
    }
    cout << endl;
    return 0;
}