『洛谷』链表

链表

链表时很基础的数据结构，大多数纯链表的题目不难，更多时候链表时解题过程中的一个工具。

在一个数列中高效插入一个元素，链表毫无疑问是最好的选择。

P1996 约瑟夫问题

题目描述

\(n\) 个人围成一圈，从第一个人开始报数,数到 \(m\) 的人出列，再由下一个人重新从 \(1\) 开始报数，数到 \(m\) 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 \(n-1\) 名小朋友，而该题是全部出圈。

输入格式

输入两个整数 \(n,m\)。

输出格式

输出一行 \(n\) 个整数，按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

1	3 6 9 2 7 1 8 5 10 4

提示

\(1 \le m, n \le 100\)

解题思路

使用循环链表模拟即可

解答代码

单向循环链表其实就可以了

#include <cstdio>
using namespace std;

const int N = 1000;
struct Node {
    int val, next;
} list[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        list[i].val = i;
        list[i].next = i + 1;
    }
    list[n].next = 1;
    // 模拟
    for (int cur = 1, i = 0; i < n; ++i, cur = list[cur].next) {
        for (int j = 2; j < m; ++j) cur = list[cur].next;
        printf("%d ", list[list[cur].next].val);
        list[cur].next = list[list[cur].next].next;
    }
    return 0;
}

P1160 队列安排

题目描述

一个学校里老师要将班上 \(N\) 个同学排成一列，同学被编号为 \(1\sim N\)，他采取如下的方法：

先将 \(1\) 号同学安排进队列，这时队列中只有他一个人；
\(2\sim N\) 号同学依次入列，编号为 \(i\) 的同学入列方式为：老师指定编号为 \(i\) 的同学站在编号为 \(1\sim(i-1)\) 中某位同学（即之前已经入列的同学）的左边或右边；
从队列中去掉 \(M\) 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 \(N\)，表示了有 \(N\) 个同学。

第 \(2\sim N\) 行，第 \(i\) 行包含两个整数 \(k,p\)，其中 \(k\) 为小于 \(i\) 的正整数，\(p\) 为 \(0\) 或者 \(1\)。若 \(p\) 为 \(0\)，则表示将 \(i\) 号同学插入到 \(k\) 号同学的左边，\(p\) 为 \(1\) 则表示插入到右边。

第 \(N+1\) 行为一个整数 \(M\)，表示去掉的同学数目。

接下来 \(M\) 行，每行一个正整数 \(x\)，表示将 \(x\) 号同学从队列中移去，如果 \(x\) 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 \(N\) 个空格隔开的整数，表示了队列从左到右所有同学的编号。

样例 #1

样例输入 #1

样例输出 #1

2 4 1

提示

【样例解释】

将同学 \(2\) 插入至同学 \(1\) 左边，此时队列为：

2 1

将同学 \(3\) 插入至同学 \(2\) 右边，此时队列为：

2 3 1

将同学 \(4\) 插入至同学 \(1\) 左边，此时队列为：

2 3 4 1

将同学 \(3\) 从队列中移出，此时队列为：

2 4 1

同学 \(3\) 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 \(20\%\) 的数据，\(1\leq N\leq 10\)。

对于 \(40\%\) 的数据，\(1\leq N\leq 1000\)。

对于 \(100\%\) 的数据，\(1<M\leq N\leq 10^5\)。

解题思路

需要随机插入、删除，适合用链表，这里使用数组模拟了链表，好处是不需要用额外的哈希表/数组记录对应同学的位置了

解答代码

#include <cstdio>
using namespace std;

const int N = 100007;
struct Node {
    int left, right;
} list[N];

int main() {
    int n, m, k, p, l = 1;
    scanf("%d", &n);
    // 初始化 1 号同学，l 记录最左边同学的编号
    list[1].left = -1, list[1].right = -1;
    for (int i = 2; i <= n; ++i) {
        scanf("%d%d", &k, &p);
        if (p == 0) { // 插入到左边
            list[i].left = list[k].left;
            list[i].right = k;
            list[k].left = i;
            if (list[i].left != -1) list[list[i].left].right = i;
            if (l == k) l = i;
        }
        else {  // 插入到右边
            list[i].left = k;
            list[i].right = list[k].right;
            list[k].right = i;
            if (list[i].right != -1) list[list[i].right].left = i;
        }
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &k);
        if (list[k].left != -1) {
            list[list[k].left].right = list[k].right;
        }
        if (list[k].right != -1) {
            list[list[k].right].left = list[k].left;
        }
        if (l == k) l = list[k].right;
        list[k].left = -1; list[k].right = -1;
    }
    for (int cur = l; cur != -1; cur = list[cur].right) {
        printf("%d ", cur);
    }
    return 0;
}