【题解】单链表

题目链接：单链表

链表

1. h 表示头结点的位置，ne[i] 表示第 i 个插入的数字所处的位置， e[i] 表示第 i 个插入的数字的值， idx 表示当前链表内节点个数。
2. 一般将 h 初始化为 -1，便于判断链表内是否为空。

关于 string

1. 由于 string 并非是 C 的原生类型，所以无法像直接输入整数那样方便的使用 scanf 函数输入 string 变量。
2. 但是是可以做到让scanf输入string类型的数据。如下代码。如果输入 hello ，则输出 he ，因为只给 a 分配了两个字符的空间。

#include <cstdio>
#include <string>
#include<iostream>
using namespace std;
int main()
{
	string a;
	a.resize(2); //需要预先分配空间
	scanf("%s", &a[0]);
	cout << a;
	return 0;
} 

数组模拟 c++ 158ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1e6 + 10;

int n;
int h = -1, ne[N], e[N], idx;

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

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

void Delete(int k)
{
    if (k == 0)
        h = ne[h];
    else ne[k] = ne[ne[k]];
}

int main()
{
    cin >> n;

    while (n -- )
    {
        char op;
        cin >> op;
        // string op; // 由于 string 并非 c 的原生类型，所以不能直接输入
        //scanf("%s", op);
        if (op == 'H')
        {
            int x; 
            scanf("%d", &x);
            add_head(x);
        }
        else if (op == 'D')
        {
            int k;
            scanf("%d", &k);
            Delete(k);
        }
        else 
        {
            int k, x;
            scanf("%d%d", &k, &x);
            add(k, x);
        }
    }

    while (h != -1)
    {
        printf("%d ", e[h]);
        h = ne[h];
    }

    return 0;
}