01_单链表 merge_interval

用数组存储链表(用空间换时间): 速度>>用new动态创建节点

#include <iostream>

using namespace std;

const int N = 100010;
/*
e[i] 表示节点的 val
ne[i] 表示节点的 next
idx 表示下一个可用节点的下标，只会递增，哪怕有节点被删，idx 也不会减少(空间换时间)
0下标代表头结点，不存储实际val，只存储next;
节点从下标 1 开始分配(idx初始为1)
*/
int m, e[N], ne[N], idx = 1;

void add(int k, int x) {
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++; // idx记得++，因为该下标已经用过了
}

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

int main() {
    cin >> m;
    while (m--) {
        char opt;
        int k, x;
        cin >> opt;
        if (opt == 'H') {
            cin >> x;
            add(0, x);
        } else if (opt == 'I') {
            cin >> k >> x;
            add(k, x);
        } else {
            cin >> k;
            remove(k);
        }
    }
    for (int i = ne[0]; i != 0; i = ne[i]) cout << e[i] << " ";

    return 0;
}

02_双链表 merge_interval

#include <iostream>

using namespace std;

const int N = 100010;
int m, e[N], ln[N], rn[N], idx = 2; // 头尾节点占了0, 1下标，idx 从 2 开始

void add(int k, int x) {
    e[idx] = x;
    rn[idx] = rn[k], ln[rn[k]] = idx;   // 先指后面
    ln[idx] = k, rn[k] = idx++;         // 再指前面; idx记得++，因为该下标已经用过了
}

void remove(int k) {
    rn[ln[k]] = rn[k], ln[rn[k]] = ln[k];
}

int main() {
    // 0下标代表头结点，1下标代表尾结点，都不存储实际val，只存储 lnext 和 rnext
    rn[0] = 1, ln[1] = 0;
    cin >> m;
    while (m--) {
        string opt;
        int k, x;
        cin >> opt;
        if (opt == "L") {
            cin >> x;
            add(0, x);
        } else if (opt == "R") {
            cin >> x;
            add(ln[1], x);
        } else if (opt == "D") {
            cin >> k;
            remove(k + 1); // 注意+1，因为第 k 个节点的下标是 k + 1
        } else if (opt == "IL") {
            cin >> k >> x;
            add(ln[k + 1], x);
        } else {
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for (int i = rn[0]; i != 1; i = rn[i]) cout << e[i] << " ";

    return 0;
}