PP4860 链表插入结点（入门）

解题思路

第一步，先弄懂题目在干什么。 题目先准备了一条链表，里面按顺序装着 1、2、3、4、5 这五个数字。然后给出两个数字 n 和 m，要求把 m 插到数字 n 的前面，最后从第一个结点开始把整条链表依次输出。比如样例里 n=3、m=9，就要把 9 放到 3 前面，得到 1 2 9 3 4 5。

第二步，想想最简单的方法。 链表里只有五个数字，我们完全可以不真的建链表，只按顺序输出：从 1 数到 5，轮到数字 n 时，先输出 m 再输出 n，其他数字照常输出。这相当于"打印的时候插队"，输出的结果和真的建链表完全一样，简单又不容易错。

第三步，注意数据范围。 题目说 m 满足 1<m<2^31，也就是 m 最大接近 21 亿，用 long long 来存才最保险。n 满足 1<n≤5，所以 n 只可能是 2、3、4、5 其中一个。

第四步，用例子验证。 如果输入 5 8，那么 1、2、3、4 依次输出后，轮到 5 先输出 8 再输出 5，结果就是 1 2 3 4 8 5，正好符合"插到 5 前面"的要求。就算 m 是很大的数，输出也不会出错。

参考代码

// 链表插入结点：把数字 m 插到数字 n 前面，再输出整个链表
#include <iostream>
using namespace std;

int main() {
    int n;
    long long m;  // m 最大接近 2^31，用 long long 保险
    cin >> n >> m;
    for (int i = 1; i <= 5; ++i) {
        if (i == n) cout << m << " ";  // 先输出 m，再输出 n
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

程序只有一层循环，循环次数固定为 5 次，每次只做几次输出，所以时间复杂度和空间复杂度都是 O(1)。因为链表里始终只有 6 个数字，数据规模不会变大，任何数据都能瞬间算完。