GESP 五级 · GESP202609 C++ 五级 第 16 题

下面代码在已知结点 p 的情况下，能够以 $O(1)$ 的时间在单链表的 p 结点之后插入新结点 s 。

s->next = p->next;
p->next = s;

这题考的是链表插入的基本操作。看到题先想指针重连的顺序：插入后 s 要指向原来 p 的下一个，p 要指向 s。关键观察是两条语句必须按特定顺序执行，否则会造成死循环或丢失链表。先 s->next = p->next 保存原后继，再 p->next = s 完成重连，两步都是常数时间赋值，没有遍历，所以时间复杂度为 O(1)。这类题的通法是：插入操作永远先连新节点的后继，再连新节点的前驱，顺序颠倒必错。

选项 B 的错误设计利用了两种常见思维陷阱。第一是操作顺序陷阱：如果先执行 p->next = s，再执行 s->next = p->next，那么 s->next 会被赋值为 s 自己，形成 s 指向 s 的死循环，链表从此断裂。第二是语义陷阱：题目强调"已知结点 p"，暗示 p 非空，但命题人故意不写 p 的合法性检查，让考生误以为需要额外判断。第三是复杂度陷阱：链表插入常被误认为需要遍历，其实只要已知前驱节点，插入就是 O(1)，命题人用这个反常识点卡住那些死记硬背"链表操作慢"的考生。

这题考的是链表插入的基本操作。看到题先想指针重连的顺序：插入后 s 要指向原来 p 的下一个，p 要指向 s。关键观察是两条语句必须按特定顺序执行，否则会造成死循环或丢失链表。先 s->next = p->next 保存原后继，再 p->next = s 完成重连，两步都是常数时间赋值，没有遍历，所以时间复杂度为 O(1)。这类题的通法是：插入操作永远先连新节点的后继，再连新节点的前驱，顺序颠倒必错。

选项 B 的错误设计利用了两种常见思维陷阱。第一是操作顺序陷阱：如果先执行 p->next = s，再执行 s->next = p->next，那么 s->next 会被赋值为 s 自己，形成 s 指向 s 的死循环，链表从此断裂。第二是语义陷阱：题目强调"已知结点 p"，暗示 p 非空，但命题人故意不写 p 的合法性检查，让考生误以为需要额外判断。第三是复杂度陷阱：链表插入常被误认为需要遍历，其实只要已知前驱节点，插入就是 O(1)，命题人用这个反常识点卡住那些死记硬背"链表操作慢"的考生。

一、代码执行流程

给定已知结点 p，要在其后插入新结点 s。代码分两步：

1. s->next = p->next; 把 s 的 next 指针指向 p 原本指向的结点。这一步保存了原后继，防止后续操作丢失链表。

2. p->next = s; 把 p 的 next 指针改为指向 s。此时链表结构变为：p → s → 原后继，插入完成。

两条语句顺序不可颠倒。若先执行第二条，p 的 next 已变为 s，再执行第一条就会让 s->next = s，形成自环，链表从此断裂且无法恢复。