题目描述

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

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

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

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

输入格式

第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。

输出格式

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

数据范围

1≤M≤100000

所有操作保证合法。

我在第一次看的时候有一些疑问做一下总结：
1.idx可以理解为一个结点，只是记录当前的操作的位置，在链表建立的过程中用来记录。
e[idx]:结点编号为idx对应的节点值。
ne[idx]：结点编号为idx对应的下一个结点的编号。

链表建立后，需要通过当前的ne[i]找到下一个idx。这也是最后输入时i=ne[i]的原因

2.在算法一中，head指针表示链表里没有内容，为空节点。当链表里有元素的时候，它变成了一个指向第一个元素的指针。在使用是作用类似ne[]。

算法1 （使用特判来处理头结点）

// 插入/删除头结点是要定义不同的操作，比如 tohead 和 head = ne[head]。

#include <iostream>

using namespace std;

const int N = 100010;
// idx的作用是指向当前可用的位置
/* 举个例子，当前单链表插入两个结点后又删除掉，
    再次插入时结点应该存储在哪？我想这时 idx = 2，
    即下标为 2 的位置是可用的，可以让head 指向这里，再创建一个单链表
*/
int e[N], ne[N], head, idx;

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

// 在链表头插入结点
void tohead(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx; // 头指针指向新插入结点的位置
    idx ++;
}

//在第k个插入的数后插入一个数
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx ++;
}

// 需要特判，保证一定是删除的非头指针指向的
void remove(int k)
{
    if (k == 0) head = ne[head];
    eles    ne[k] = ne[ne[k]];
}

int main()
{
    int n;
    cin >> n;
    init();
    for (int i = 0; i < n; i ++)
    {
        char op;
        cin >> op;
        if (op == 'H') {
            int x;
            cin >> x;
            tohead(x);
        }
        if (op == 'D') {
            int k;
            cin >> k;
            remove(k - 1);
        }
        if (op == 'I') {
            int k, x;
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    // i 根据当前结点的指针域指向下一个结点
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
}

算法2

思考对算法一的改进，我们发现需要对头结点进行特判，可以用什么方法来解决这个问题呢？
我们可以直接不使用head来表示指向下一个结点的位置，直接用0来表示指向首元结点的位置。
题目要求分开对头结点插入的讨论，如果不做要求我们也可以和删除一样，用k=0来一般表示。

我们还发现使用到k时都是用的k-1；我们可以使idx结点的起始+1，消去这个-1。

include <iostream>

using namespace std;

const int N = 100010;
int e[N], ne[N];
int m, idx;

void init()
{
    ne[0] = -1;
    idx = 1;
}

void tohead(int x)
{
    e[idx] = x;
    ne[idx] = ne[0];
    ne[0] = idx;
    idx++;
}

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

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

int main()
{
    cin >> m;

    init();

    while (m -- )
    {
        char op;
        cin >> op;

        int k, x;
        if (op == 'H')
        {
            cin >> x;
            tohead(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            remove(k);
        }
        else if (op == 'I')
        {
            cin >> k >> x;
            add(k, x);
        }
    }

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