题目描述

双链表,想说的都在注释中了.
说的不到位的.(欢迎dalao)
还请大家执教 orz !

算法1

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

参考文献

y总

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010;

int e[N], l[N], r[N], idx;

void init()
{   
    //记住 : 数组[] 中括号中的数都代表的是在链表中的位置.
    r[0] = 1;// 0 代表链表中的第 0 个位置, r[0] = 1 代表链表中的第 0 个位置的右next指针指向链表中的第一个位置.
    l[1] = 0;// 1 代表链表中的第 1 个位置, l[1] = 0 代表链表中的第 1 个位置的左next指针指向链表中的第零个位置.
    idx = 2; // 由于上面的操作,链表中两个位置已经被用了,idx 表示已经用过的位置.也代表下一个插入的数应该在链表中 2 的位置
    //实际链表: 0  (待插入)  1 
    //位置下标: 0     2      1
}

//这里是在第k个位置右边插入一个数(k从0开始,数k表示链表中第k个位置)
void insert(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    //这里一定先是左指针,再是右指针.
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;// idx 移动到下一个位置
}

//去除
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    int m;
    cin >> m;
    init();

    while (m --)
    {
        string op;
        int k, x;
        cin >> op;

        if (op == "L")//在第 0 个位置的右边插入一个数.
        {
            cin >> x;
            insert(0, x);
        }
        else if (op == "R")//在第 1 个位置的左next指针所指向的位置的右侧插入一个数.
        {
            cin >> x;
            insert(l[1], x);
        }
        else if (op == "D")//将第 k 个位置的数,删除.
        {
            //注意 : 题目中的 k 是从 1 开始的, 并且第 k 个插入的链表中的位置是 k - 1 + 2;
            //k - 1 是实际上第几个插入的数
            // + 2 是因为链表中的位置是从 2 开始递增的.
            cin >> k;
            remove(k + 1);
        }
        else if (op == "IR")
        {   
            cin >> k >> x;
            insert(k + 1, x);
        }
        else
        {
            cin >> k >> x;
            insert(l[k + 1], x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';//这里不能用 i = 2 ,因为 2 这个位置的数有可能被删除.
    //但 r[0] 一定是 从左往右的第一个数.
    cout << endl;
    return 0;
}