CSP-J 2022 第一轮 第 11 题：双向循环链表插入结点的正确操作顺序

题目

以下哪组操作能完成在双向循环链表结点 $p$ 之后插入结点 $s$ 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：（ ）。

选项

• A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• B. p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• C. s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• D. s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

答案

D

题解

正确答案是 D。

设 p 原来的后继是 q，插入前后关系为：

``text 插入前：p ⇄ q 插入后：p ⇄ s ⇄ q ``

因此需要让四个指针分别指向：

``cpp s->next = p->next; // s 的后继是原来的 q p->next->prev = s; // q 的前驱改为 s s->prev = p; // s 的前驱是 p p->next = s; // p 的后继改为 s ``

这正是选项 D。关键是：修改 p->next 后，它就指向 s，不能再用它访问原来的后继 q。

其余选项的问题：

• A、B：先执行了 p->next=s，再执行 s->next=p->next，导致 s->next=s。
• C：执行 p->next=s 后，p->next->prev=s 就等于 s->prev=s，导致 s 的前驱指向自己。