NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 13 题

双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 $p$ 指向链表中的一个结点，$q$ 指向一待插入结点，现要求在 $p$ 前插入 $q$，则正确的插入为（ ）。

这题考双向链表插入。思路很简单：先别动 p 的指针，把 p 的前驱连向 q，再把 q 连向 p 和前驱，最后才把 p 的 llink 指向 q。顺序错了链表就断了。

最容易错的就是第一步就改 p->llink = q，这样 p 原来的前驱就找不到了，后续 p->llink->rlink 直接报错或逻辑错。还有学生喜欢按 A 选项那样先改 p->llink 再改前驱的 rlink，其实应该先改前驱的 rlink，保证旧指针还在。另外 C 选项里 p->rlink = q 是多余的，题目只要求在 p 前插，p 的后继不该动。D 选项顺序完美，先连旧前驱，再连新节点，最后连 p。

考点概念：双向链表插入

在双向链表中，每个结点有两个指针：llink 指向前驱，rlink 指向后继。要在结点 p 之前插入结点 q，核心原则是：先处理旧指针，再更新新指针，避免断链。因为一旦 p->llink 被修改，我们就再也找不到 p 原来的前驱了，后续操作就会出错。

命题视角：为什么考这个顺序？

命题人特别喜欢在这种“插入/删除”题里挖坑，主要就两个方向： 1. 顺序陷阱：先改 p->llink = q 还是先改 p->llink->rlink = q？前者会丢失前驱，后者安全。 2. 多余操作陷阱：比如选项 C 里多了一个 p->rlink = q，这是干扰项，因为插入在 p 前面，p 的后继本来就不该动。

思考心法：拿到题先想什么？

拿到“在 p 前插入 q”这种题，脑子里要立刻过一遍四步逻辑（假设 pre = p->llink）： 1. 先把 pre 的后继指向 q：pre->rlink = q（保证 pre 还能连上 q）。 2. 让 q 的后继指向 p：q->rlink = p（q 插入后紧跟 p）。 3. 让 q 的前驱指向 pre：q->llink = pre（即 q->llink = p->llink）。 4. 最后才把 p 的前驱指向 q：p->llink = q（完成插入）。

这四步必须按这个顺序，因为前两步是在“旧指针”上操作，后两步才是“新指针”的更新。只要第一步动了 p->llink，后面的 pre->rlink = q 就没法写了。

具体怎么算（逐项分析）

• A 选项：p->llink = q 第一步就改了，p 原来的前驱丢了，后面 p->llink->rlink = q 实际上是 q->rlink = q，逻辑全乱，错误。
• B 选项：q->llink = p->llink 是对的，但后面 p->llink = q->rlink 这里 q->rlink 还没被赋值为 p，此时 q->rlink 是 NULL，导致 p->llink = NULL，链表断掉，错误。
• C 选项：多了一个 p->rlink = q，这是多余操作，而且 q->rlink = p 只写了一次，后面又写一次 q->rlink = p 重复，逻辑混乱，错误。
• D 选项：p->llink->rlink = q（第一步改旧前驱的后继），q->rlink = p（q 后继连 p），q->llink = p->llink（q 前驱连旧前驱），p->llink = q（最后 p 前驱连 q）。四步顺序完美，正确。

避坑提醒

做题时千万别被“先改 p->llink”这种直觉带偏，一定要记住：插入前，先连旧指针，再动新指针。否则链表就断了，程序直接崩。

考频与趋势

根据真实数据，图论算法在题库中已考过 26 题，覆盖 3 个级别。逐年分布：2015 年 2 题、2016 年 1 题、2017 年 1 题、2019 年 1 题、2021 年 1 题、2024 年 1 题、2025 年 2 题、2026 年 5 题、null 年 12 题。分赛事：CSP 入门级 14 题、CSP 提高级 8 题、NOIP 提高组 初赛 4 题。这道双向链表插入题正是图论基础中的经典考点，属于高频易错点。

预测

从历年趋势看，图论相关题目在 2025-2026 年明显增多（2025 年 2 题、2026 年 5 题），说明命题人越来越重视数据结构与算法基础。未来可能继续考链表操作、树遍历等基础图论题，尤其是“插入/删除”这类容易出顺序陷阱的题目，大概率还会以单选题形式出现，继续挖“先改谁后改谁”的坑。暂无足够依据预测具体年份和题号，但考生应重点复习链表和树的基本操作顺序。