链表 知识点讲解

🎯 先搞清楚它是什么

📌 考纲要求（NOI 大纲 · 数据结构基础 / 参考《cspNOI级大纲解读》）：考纲在“线性结构”的 GO 参考词条中明确列出：“链表：单链表、双向链表、循环链表”。正文也以“块状链表”为例对比了三种结构的插入、查询、删除复杂度（数组 O(n)/O(1)/O(n)，链表 O(1)/O(n)/O(1)）。本讲对齐“链表”这一考点：理解结点 + 指针的链式存储，以及它相对数组的优劣。

链表（linked list） 不要求内存连续。它由一个个结点（node）组成，每个结点存“数据”和“指向下一个结点的指针（next）”。结点们像火车车厢一样一节挂一节。

三种常见形态：

• 单链表：每个结点只记“下一个是谁”（next）；
• 双向链表：还记“上一个是谁”（prev），可前后走；
• 循环链表：尾结点的 next 指向头，首尾相连成环。

⚠️ 核心对比：数组“随机访问快（O(1)）但中间插入删除慢（O(n)）”；链表反过来——插入删除只要改几个指针 O(1)，但找第 k 个结点得从头走 O(n)。所以“频繁在中间插删”用链表，“频繁按下标取”用数组。

🧩 关键规则与结论

手写单链表（结构体 + 指针）：

struct Node { int val; Node* next; };
Node* head = nullptr;                 // 头指针，空链表 head 为 null

// 头插法：新结点插在最前面
Node* p = new Node{x, head}; head = p;

// 删除 p 的后继
Node* q = p->next; p->next = q->next; delete q;

数组模拟链表（静态链表，竞赛最爱，无指针风险）：

int val[N], nxt[N], head = -1;        // nxt[i] 表示 i 的下一个结点编号，-1 表示无
// 头插：新结点编号为 id
nxt[id] = head; head = id;

三条铁律：

1. 插入/删除前想清楚“先连后断”还是“先断后连”，别先把要用的指针覆盖掉；

2. 遍历到 next == nullptr（或 nxt==-1）就到表尾，再走会越界；

3. 删除结点记得释放（delete 或标记），否则内存泄漏（竞赛一般不计较，但要逻辑对）。

🗺️ 知识用法地图

🔬 推演：为什么这些写法是对的（以及它们能用来干什么）

推演 1 · 为什么插入只要 O(1)

在结点 p 后面插入新结点 q：只需 q->next = p->next; p->next = q;。操作数固定（两条赋值），与链表多长无关 → O(1)。对比数组：在中间插入要把后面所有元素后移一位 O(n)。这就是链表省时间的地方。

📌 用法：数组插删慢在“搬数据”，链表插删只是“改指针”，所以插删密集用链表。

推演 2 · 为什么“先连后断”才不会丢链子

插入 q 到 p 后：如果先写 p->next = q，那么 p 原来的后继就找不回来了，再写 q->next = p->next 时 p->next 已经是 q 自己 → 链表断了/成环。正确顺序是先让 q 接到旧后继，再让 p 接到 q（先连后断），旧链始终可达。

📌 用法：写任何“改指针”操作，先把新关系接上、最后才改旧的，避免悬空指针。

推演 3 · 为什么约瑟夫环用循环链表

n 个人围成一圈，每数到 m 出列。循环链表的尾 next 指向头，没有“边界”，报数到末尾自动绕回开头，完美对应“环形”。出列就是删一个结点，O(1)。手写时也可以不用真链表，用 vector 不断 erase 模拟（慢但好写），或用数学递推。

📌 用法：凡是“围成圈、轮流出”的题，循环链表或取模下标天然匹配。

🔧 编程题里怎么考、怎么用？

① 它在编程题里长什么样（考法总览）

② 识别信号清单：看到什么该想到链表

• “频繁在中间插入/删除” → 链表；
• “围成一圈、轮流出列” → 循环链表 / 约瑟夫；
• “插到某人左边/右边、按顺序排” → 双向/静态链表；
• “和前一个/后一个比较” → 双向链表；
• 若怕指针写崩，直接用数组模拟（静态链表）。

判断步骤：

① 插删多还是按下标取多？插删多 → 链表
② 是不是环状？→ 循环链表 / 取模
③ 怕指针？→ 静态链表（数组 + nxt）

③ 必背模板：静态单链表（头插 + 遍历）

const int N = 100005;
int val[N], nxt[N], head = -1, cnt = 0;
// 头插一个新值 v
int id = ++cnt; val[id] = v; nxt[id] = head; head = id;
// 遍历
for (int p = head; p != -1; p = nxt[p]) cout << val[p] << ' ';

④ 必背模板：约瑟夫环（取模模拟，不用真链表）

// n 个人，每数到 m 出列，求最后剩下的人（编号 1..n）
int last = 0;
for (int i = 2; i <= n; i++) last = (last + m) % i;   // ⭐ 递推：每轮规模 +1
cout << last + 1 << '\n';                              // 还原到 1 基编号

⑤ 思路点拨：拿到题第一步想什么

1. 先判断用真指针还是静态链表——竞赛绝大多数用静态链表更稳；

2. 画三格图：当前结点 p、前驱、后继，想清楚改哪根指针；

3. “先连后断”，保留旧链可达；

4. 循环条件 p != -1 / nullptr，别走到空还继续；

5. 约瑟夫类可先想数学递推，再想模拟。

📚 更多同类真题（来自真题库，点击展开）

🔍 看一个例子

例：用静态链表做“头插建表 + 遍历”（核心骨架）。

#include <iostream>
using namespace std;
const int N = 100005;
int val[N], nxt[N], head = -1, cnt = 0;
int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int v; cin >> v;
        int id = ++cnt;            // 分配新结点编号
        val[id] = v;
        nxt[id] = head;            // ⭐ 先让新结点接到旧头
        head = id;                 // ⭐ 再让头指针指向新结点（先连后断）
    }
    for (int p = head; p != -1; p = nxt[p])   // ⭐ 顺着 next 走到 -1（表尾）
        cout << val[p] << ' ';
    return 0;
}

下面对照一张图理解“结点靠指针串起来”：

🪤 常见错误

1. “先断后连”丢链子：插入时先 p->next=q 再 q->next=p->next，旧后继丢了、还成环。务必先连后断。

2. 遍历到空还继续：for(; p; p=p->next) 当 p 为 nullptr 时再访问 p->next 会崩，循环条件要 p != nullptr。

3. 指针没初始化：next 不初始化可能是野指针，数组模拟要置 -1。

4. 头指针为空的特判：空表插入要走“新建头结点”分支，别直接解引用 head。

5. 约瑟夫取模编号错：递推 f[i]=(f[i-1]+m)%i 是基于 0 基，最后要 +1 还原成 1 基。

6. 混淆链表与数组下标：链表没有“第 i 个=O(1)”，要第 k 个得从头走 k 步。

✅ 自测

1. 单链表、双向链表、循环链表分别多记了什么指针？

2. 为什么链表在中间插入是 O(1)、数组是 O(n)？

3. 插入 q 到 p 之后，为什么“先连后断”才安全？写出正确两条语句。

4. 静态链表用哪两个数组代替指针？head=-1 表示什么？

5. 约瑟夫环为什么适合用循环链表？不用链表还能怎么解？

6. 遍历链表时循环条件写什么？走到空还访问 next 会怎样？

7. 数组和链表分别什么时候该用？给出一个“该用链表却用数组会慢”的场景。

这个模型讲什么

链表用“结点 + 指针”把数据串起来，每个结点存“数据”和“下一个结点的地址（next）”。不要求内存连续，所以中间插删只要改指针。

// 真指针版
struct Node { int val; Node* next; };
Node* head = nullptr;                 // 头指针，空表为 null
// 头插：新结点插最前
Node* p = new Node{x, head}; head = p;
// 删除 p 的后继
Node* q = p->next; p->next = q->next; delete q;

// 静态链表（数组模拟，竞赛常用、无指针风险）
int val[N], nxt[N], head = -1, cnt = 0;
int id = ++cnt; val[id] = v; nxt[id] = head; head = id;   // 头插
for (int p = head; p != -1; p = nxt[p]) cout << val[p];    // 遍历

关键概念

• 单链表：只记 next；双向：还记 prev；循环：尾 next 指向头；
• 先连后断：插入时先 q->next = p->next 再 p->next = q，否则旧链丢失；
• 遍历终止：next == nullptr（或 -1），再走越界。

易错：插入顺序写反会丢链子；遍历到空还访问 next 会 RE；head 为空要单独处理。

练这几道（从易到难）

P1160 队列安排（按位置插入）→ P1996 约瑟夫问题（环形出列）→ P3156 询问学号（基础增删）。

这个模型讲什么

链表的典型应用集中在“环”和“频繁插删”两类题。

① 约瑟夫环（循环链表天然匹配）：n 个人围成圈，每数到 m 出列。循环链表的尾 next 指向头，没有边界，报数到末尾自动绕回，出列即删结点。

// 数学递推版（最稳，不用真链表）：f[1]=0, f[i]=(f[i-1]+m)%i，最后 +1
int last = 0;
for (int i = 2; i <= n; i++) last = (last + m) % i;
cout << last + 1;

② 在某人左边/右边插入（队列安排 P1160）：用双向/静态链表，定位到目标结点后改两根指针即可，O(1)。

③ 找前驱/后继（营业额统计 P2234）：有序结构里“左边最近 / 右边最近”正是双向链表的强项（prev/next），可用 set 的 lower_bound 近似。

关键提醒

• 约瑟夫类题优先写递推，再考虑模拟；
• 怕指针就用静态链表（数组 + nxt[]）；
• 递推的 %i 是 0 基，结果记得 +1 还原 1 基编号。

练这几道（从易到难）

P1996 约瑟夫问题（环+出列）→ P2234 营业额统计（前后邻）→ P3613 寄包柜（二维存取模拟）。