链表CSP-J

💡 核心思想

链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。在竞赛中，通常用数组模拟链表（因为不需要动态分配内存，速度更快）。常见变体：单链表、双链表、循环链表。

🎯 直觉理解

链表就像一列火车——每节车厢连着下一节。你要插入一节车厢，只需要把它前面的车厢连到新车厢，新车厢连到后面的车厢。删除也类似，把前后的车厢直接连起来就行。

📝 算法流程

1. 数组模拟：val[], nxt[], pre[]
2. 头插法/尾插法
3. 删除：修改前后节点的指针
4. 遍历：从 head 开始沿 nxt 走

$$\text{插入/删除：} O(1)，\text{查找第k个：} O(k)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int val[N], nxt[N], head, tot;
void init() { head = -1; tot = 0; }
void insertHead(int x) { val[tot] = x; nxt[tot] = head; head = tot++; }
void insertAfter(int k, int x) { val[tot] = x; nxt[tot] = nxt[k]; nxt[k] = tot++; }
int main() {
    init();
    int n; cin >> n;
    for (int i = 0; i < n; i++) { int x; cin >> x; insertHead(x); }
    for (int i = head; i != -1; i = nxt[i]) cout << val[i] << " ";
    return 0;
}

⚠️ 常见坑点

📚 相关题目