NOIP 提高组初赛 · NOIP 2014 提高组初赛试题 第 11 题

有以下结构体说明和变量定义，如图所示，指针 $p,q,r$ 分别指向一个链表中的三个续结点。 

struct node {   
 int data;  
 struct node *next;    
} *p,*q,*r;

现要将 $q$ 和 $r$ 所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )

这道题考的是链表结点交换时指针顺序的把控。拿到题先想：p、q、r 是相邻三结点头尾，交换 q 和 r 后链表仍要连续。关键是要先保存好 q 原来的后继，再改 p 指向 r，最后把 r 指回 q，绝对不能先让 r 去改 q 的 next，否则 q 会断链。

最容易掉进的坑就是 D 选项那种‘先动 r 的 next’。学生往往觉得只要最后 p 连上 r 就行，却忘了链表是单向的，一旦 r->next 被改成 q，q 原本指向的后继就彻底丢了，后面再去改 q->next 时，它只能看到 r->next（也就是 q 自己），结果形成自环。还有一个常见误区是以为交换完 q 和 r 后，p 的 next 不需要再动，其实 p 原本连的是 q，q 换成了 r，p 必须改连 r 才能保持链表不断。

链表节点交换

初始：p→q→r 目标：p→r→q

选项 D 的错误

r->next = q;      // 第一步：r 指向 q，但 r 原来的 next 丢失
q->next = r->next; // 第二步：r->next 已经变成了 q，所以 q->next = q(自指)
p->next = r;       // 第三步：p 指向 r

交换节点必须用临时变量保存断点，先连接后断开。

结论：D 选项错误，答案选 D。

正确做法（A、B、C 为何都对）

三个正确选项的共同点是： 1. 先保存 q 原来的后继（用 r->next 或临时变量）； 2. 改 p 指向 r； 3. 再把 r 指回 q。

• A：q->next = r->next; p->next = r; r->next = q;

第一步把 q 的后继暂存到 r->next，第二步 p 连 r，第三步 r 连 q，完美。

• B：p->next = r; q->next = r->next; r->next = q;

先改 p 连 r，再把 q 连到 r 原来的后继，最后 r 连 q，也完美。

• C：q->next = r->next; r->next = q; p->next = r;

先暂存 q 的后继，再让 r 连 q，最后 p 连 r，同样完美。

命题人怎么挖坑

这道题属于“程序填空/阅读程序”的典型套路：给出一个看似简单的交换片段，让你判断哪一行会破坏链表连续性。命题人喜欢在交换节点时故意让你先动“中间”指针的 next，从而制造自环或断链。这类坑在历年的链表题里反复出现，尤其是当题目只给了三个相邻指针时，学生很容易忽略 p 也需要跟着变。

考频与趋势

链表是 NOIP 和 CSP 的高频考点。题库共考过 81 题，覆盖 7 个考试级别（2009-2026）。逐年分布：2009 年 1 题、2010 年 2 题、2011 年 1 题、2014 年 3 题、2015 年 3 题、2018 年 2 题、2019 年 1 题、2020 年 1 题、2022 年 2 题、2023 年 6 题、2024 年 26 题、2025 年 16 题、2026 年 10 题、null 年 7 题。分赛事：GESP 五级 42 题、GESP 六级 11 题、GESP 七级 7 题、NOIP 普及组 初赛 6 题、NOIP 提高组 初赛 6 题、CSP 入门级 5 题、GESP 八级 4 题。

从数据看，2024 年链表题突然暴增到 26 题，2025 年又回落至 16 题，2026 年还有 10 题，说明链表依然是命题人重点关注的结构。未来可能继续以“链表操作+指针顺序”的形式出现，比如插入、删除、合并、回环检测等，但核心还是考查你是否会先保存断点再改指针。

暂无足够依据预测未来具体会考哪一道链表题，但链表作为数据结构基础，几乎每年必现，尤其是提高组初赛和 CSP 入门级，建议把链表交换、插入、删除等模板练熟，避免在考场上掉进自环或断链的坑。