B4324 【模板】双向链表

chen_zhe · 2025-11-24 12:11:41 · 题解

这是一篇由 AI 生成的题解，讲解以及代码正确性已经经过人工核验，可以用于学习双向链表。

使用数组模拟双向链表。我们可以定义两个数组 l[] 和 r[]。对于编号为 i 的节点，l[i] 存储它左边节点的编号，r[i] 存储它右边节点的编号。这样，我们就可以在 O(1) 的时间内直接访问任意节点并在其前后进行插入或删除操作，而不需要遍历整个链表。

为了方便处理链表的头和尾，我们可以引入一个“虚拟节点” 0。我们规定 r[0] 指向链表的第一个真实节点。如果 r[0] 最终还是 0，说明链表为空。

1. 初始化：构建初始链表。对于节点 i，它的左边是 i-1，右边是 i+1。特别地，0 的右边是 1，N 的右边是 0（表示链表结束）。
2. 删除操作（Unlink）：为了移动或删除节点 x，我们需要先把它从当前位置“摘除”。方法很简单：让 x 左边的节点直接指向 x 右边的节点，反之亦然。
3. 插入操作（Link）：将节点 x 插入到节点 p 的右侧。我们需要更新四个指针：x 的左右、p 的右以及原 p 右边节点的左。
4. 指令处理：
   • 指令 1（插到左侧）：等同于将 x 插入到 y 左边节点的右侧。
   • 指令 2（插到右侧）：直接将 x 插入到 y 的右侧。
   • 指令 3（删除）：将 x 摘除，并标记为永久删除。

#include <iostream>

// 使用 std 命名空间
using namespace std;

// 定义最大节点数，稍微开大一点防止越界
const int MX = 500005;

// l[i] 记录 i 左边的节点，r[i] 记录 i 右边的节点
int l[MX], r[MX];

// del 数组用来标记节点是否被永久删除，true 表示已删除
bool del[MX];

// 辅助函数：将节点 x 从当前链表中摘除
// 注意：这只是断开链接，并没有永久删除数据
void rm(int x) {
    // 让 x 左边的节点直接连向 x 右边的节点
    r[l[x]] = r[x];
    // 让 x 右边的节点直接连向 x 左边的节点
    l[r[x]] = l[x];
}

// 辅助函数：将节点 x 插入到节点 p 的右边
void ins(int p, int x) {
    // 设置 x 自身的左右指针
    l[x] = p;
    r[x] = r[p];

    // 更新 p 右边那个节点的左指针指向 x
    l[r[p]] = x;
    // 更新 p 的右指针指向 x
    r[p] = x;
}

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    // 初始化链表
    // 0 号节点作为虚拟头节点
    r[0] = 1; 

    // 构建 1 到 n 的初始链接
    for (int i = 1; i <= n; ++i) {
        l[i] = i - 1;
        r[i] = i + 1;
    }
    // n 号节点的右边没有节点，设为 0
    r[n] = 0; 

    // 处理 m 条指令
    while (m--) {
        int op, x, y;
        cin >> op;

        if (op == 1) {
            cin >> x >> y;
            // 如果 x 和 y 是同一个点，或 x 已删除，则忽略
            if (x == y || del[x]) continue;

            // 移动 x 到 y 的左边
            // 先把 x 从原位置摘除
            rm(x);
            // y 的左边就是 l[y]，把 x 插到 l[y] 的右边
            ins(l[y], x);
        } 
        else if (op == 2) {
            cin >> x >> y;
            if (x == y || del[x]) continue;

            // 移动 x 到 y 的右边
            rm(x);
            // 直接把 x 插到 y 的右边
            ins(y, x);
        } 
        else if (op == 3) {
            cin >> x;
            // 如果 x 已经被删除，则忽略
            if (del[x]) continue;

            // 摘除 x 并标记为永久删除
            rm(x);
            del[x] = true;
        }
    }

    // 输出结果
    // 从虚拟头节点 0 的右边开始遍历
    int cur = r[0];

    if (cur == 0) {
        // 如果 0 的右边还是 0，说明链表为空
        cout << "Empty!";
    } else {
        // 只要没走到 0 (链表末尾)，就一直输出
        while (cur != 0) {
            cout << cur << " ";
            cur = r[cur];
        }
    }
    cout << endl;

    return 0;
}

Python 代码：

import sys

# 增加递归深度限制，虽然本题主要用迭代，但这是一个好习惯
sys.setrecursionlimit(20000)

def main():
    # 使用 sys.stdin.read() 一次性读取所有输入内容
    # split() 会自动按空白字符（空格、换行）分割成字符串列表
    data = sys.stdin.read().split()

    # 将输入数据转换为迭代器，方便逐个获取
    iterator = iter(data)

    try:
        # 获取 N 和 M
        n = int(next(iterator))
        m = int(next(iterator))
    except StopIteration:
        return

    # 初始化数组模拟链表
    # l[i] 表示 i 左边的节点，r[i] 表示 i 右边的节点
    # 列表大小设为 n + 2 以防止越界
    # l 初始化：l[1]=0, l[2]=1, ...
    l = list(range(-1, n)) 
    # r 初始化：r[0]=1, r[1]=2, ...
    r = list(range(1, n + 2))

    # 修正边界
    r[n] = 0  # n 的右边没有节点，设为 0 表示结束

    # d[i] 用来标记节点 i 是否被永久删除
    d = [False] * (n + 1)

    # 处理 m 条指令
    for _ in range(m):
        op = int(next(iterator))

        if op == 1: # 将 x 插入到 y 的左侧
            x = int(next(iterator))
            y = int(next(iterator))

            # 如果 x 等于 y 或 x 已删除，忽略
            if x == y or d[x]:
                continue

            # 1. 先把 x 从原来的位置摘除
            lx, rx = l[x], r[x]
            r[lx] = rx # x左边的节点的右指针指向x的右边
            l[rx] = lx # x右边的节点的左指针指向x的左边

            # 2. 将 x 插入到 y 的左侧
            # 等同于插入到 l[y] 的右侧
            p = l[y]

            # 连接 x 和它周围的新节点
            r[x] = r[p] # x 的右边变成 p 的右边（也就是 y）
            l[x] = p    # x 的左边变成 p

            l[r[p]] = x # 原来 p 右边节点（y）的左指针指向 x
            r[p] = x    # p 的右指针指向 x

        elif op == 2: # 将 x 插入到 y 的右侧
            x = int(next(iterator))
            y = int(next(iterator))

            if x == y or d[x]:
                continue

            # 1. 摘除 x
            lx, rx = l[x], r[x]
            r[lx] = rx
            l[rx] = lx

            # 2. 将 x 插入到 y 的右侧
            p = y

            r[x] = r[p]
            l[x] = p

            l[r[p]] = x
            r[p] = x

        elif op == 3: # 删除节点 x
            x = int(next(iterator))

            if d[x]:
                continue

            # 摘除 x
            lx, rx = l[x], r[x]
            r[lx] = rx
            l[rx] = lx

            # 标记为永久删除
            d[x] = True

    # 输出结果
    res = []
    # 从虚拟头节点 0 的右边开始
    curr = r[0]

    # 遍历链表收集结果
    while curr != 0:
        res.append(str(curr))
        curr = r[curr]

    if not res:
        print("Empty!")
    else:
        # 使用 join 快速合并字符串并输出
        print(" ".join(res))

if __name__ == "__main__":
    main()