408 高频考点精讲:链表(Linked Lists (Singly Linked, Doubly Linked, Circular, Fast-Slow Pointers))¶
模块归属:数据结构 · 线性表
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:6 次(2016~2025 年:2016#1、2016#2、2019#41、2021#1、2023#2、2024#1)
- 历年总考查频次:9 次(包含 2009#42 查找倒数第 \(k\) 个结点、2012#42 共享后缀起始结点、2015#41 删除绝对值重复结点)
- 出题形式:单项选择题(占比约 60%)与综合应用算法设计题(分值 13~15 分,占比约 40%)并重。
- 命题特点:
- 指针时序依赖为选择题高频核心:重点考查单链表、双向链表、循环链表在插入与删除操作中的指针赋值时序,严查断链、指针悬空与内存泄漏。
- 边界条件测试极其严苛:命题频繁针对单元素链表、首元结点处理、尾指针退化等极端边界设防(如 2021 年第 1 题)。
- 算法大题高度青睐 \(O(1)\) 辅助空间原地重组:历年大题聚焦于快慢指针定位、原地逆置、两路交织归并等核心模式的组合运用(如 2019 年第 41 题)。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
√ - - √ - √ - √ √ -
(#1, #2) (#41) (#1) (#2) (#1)
二、 具体考察内容¶
1. 链式存储结构的形式化定义与分类拓扑¶
线性表的链式存储结构使用任意的存储单元存储逻辑上相邻的数据元素。元素之间的逻辑关系通过附加的指针字段显式维护。
(1) 单链表(Singly Linked List)¶
每个结点仅包含一个指向其直接后继结点的指针域。
typedef struct LNode {
ElemType data; /* 数据域 */
struct LNode *next; /* 指针域,指向直接后继结点 */
} LNode, *LinkList;
(2) 双向链表(Doubly Linked List)¶
每个结点包含两个指针域,分别指向其直接前驱与直接后继,克服单链表无法逆向遍历的缺陷。
typedef struct DNode {
ElemType data; /* 数据域 */
struct DNode *prev; /* 指针域,指向直接前驱结点 */
struct DNode *next; /* 指针域,指向直接后继结点 */
} DNode, *DLinkList;
(3) 循环链表(Circular Linked List)¶
- 单向循环链表:尾结点的 \(next\)$ \text{指针不再指向} $\(\text{NULL}\),而是指向头结点,整个链表形成单向环路。
- 双向循环链表:头结点的 \(prev\)$ \text{指向尾结点,尾结点的} $\(next\) 指向头结点,形成双向闭环。
(4) 静态链表(Static Linked List)¶
借助一维数组模拟链式存储结构,数组分量包含数据域 \(data\)$ \text{和游标域} $\(cur\)。游标替代指针,记录后继元素在数组中的下标。 * 物理上连续分配,逻辑上通过游标离散链接。 * 适用于无指针类型支持的高级程序设计语言或固定容量场景。
(5) 头结点(Dummy Head Node)的机制与代数优势¶
头结点位于链表首元结点之前,通常不存放线性表有效数据元素。 * 统一操作逻辑:无论在链表第 1 个位置插入/删除,还是在其余位置插入/删除,前驱指针均为非空指针,无需对首元结点编写特殊分支代码。 * 统一空表非空表判定:带头结点的链表,其头指针 \(head\) 恒不为空,仅需判断其后继指针。
各链表形态判空条件对照表:
| 链表类别 | 带头结点判空条件 | 不带头结点判空条件 |
|---|---|---|
| 单链表 | head->next == NULL |
head == NULL |
| 双向链表 | head->next == NULL |
head == NULL |
| 单向循环链表 | head->next == head |
head == NULL |
| 双向循环链表 | head->next == head(或 head->prev == head) |
head == NULL |
2. 基本操作指针重构与操作时序安全性定理¶
(1) 基址保护与时序依赖定理¶
基址保护定理:在无额外临时指针备份的前提下,若修改某一结点的指针域导致其后继结点的内存地址无法通过现有指针链寻址,则会发生不可逆断链,引发内存泄漏或程序异常。
(2) 单链表后插与前插操作¶
- 后插操作(在结点 \(p\)$ \text{之后插入结点} $\(s\)):
必须先挂接新结点的后继,再修改原结点的后继指针:
若颠倒次序(执行
p->next = s; s->next = p->next;),则s->next将指向自身,导致原后继子链永久丢失。 - 前插操作(在结点 \(p\)$ \text{之前插入结点} $\(s\)$ \text{的} $\(O(1)\) 实现): 由于单链表无前驱指针,若不从头遍历寻找 \(p\) 的前驱,可采用数据域偷换法:
(3) 双向链表插入操作¶
在结点 \(p\)$ \text{之后插入新结点} $\(s\)$ \text{(设} $\(p\) 存在后继结点): 需维护 4 个方向的指针指向:
s->next = p->next; /* 步骤 1:s 指向原后继 */
p->next->prev = s; /* 步骤 2:原后继回指 s */
s->prev = p; /* 步骤 3:s 回指 p */
p->next = s; /* 步骤 4:p 指向 s */
p->next = s;),原后继结点的基址只能通过 s->next 获取,此时必须利用 s->next->prev = s; 完成回指更新(对应 2023 年第 2 题)。
(4) 结点的删除操作¶
- 单链表删除结点 \(p\)$ \text{的后继结点} $\(q\):
- 单链表在 \(O(1)\)$ \text{时间内删除指定结点} $\(p\)(\(p\) 非尾结点): 将后继结点的数据复制给 \(p\)$ \text{,随后转化为删除} $\(p\) 的后继结点:
- 双向循环链表删除指定结点 \(p\):
3. 单链表原地逆置两大核心范式¶
链表原地逆置要求空间复杂度为 \(O(1)\),是 408 综合算法题的核心基础组件。
(1) 范式一:头插迭代法(Head-Insertion Paradigm)¶
将原链表解构为“新头结点”与“待插入结点链表”,顺序摘下每个结点,插在头结点的直接后继处。
LinkList ReverseByHeadInsert(LinkList L) {
LNode *p = L->next; /* p 为工作指针,指向当前待逆置结点 */
L->next = NULL; /* 断开头结点,将其初始化为一个空链表 */
while (p != NULL) {
LNode *r = p->next; /* 暂存后继结点,防止断链 */
p->next = L->next; /* 将 p 插入到头结点之后 */
L->next = p;
p = r; /* 推进到下一个待处理结点 */
}
return L;
}
(2) 范式二:三指针滑动翻转法(Three-Pointer Sliding Window)¶
不依赖头结点,使用 prev、curr、next_node 三个连续指针,原地逐一翻转结点的指针指向。
LNode* ReverseList(LNode *head) {
LNode *prev = NULL;
LNode *curr = head;
while (curr != NULL) {
LNode *next_node = curr->next; /* 1. 暂存原后继 */
curr->next = prev; /* 2. 局部指针逆向翻转 */
prev = curr; /* 3. 前驱指针右移 */
curr = next_node; /* 4. 当前指针右移 */
}
return prev; /* 返回逆置后的新头指针 */
}
4. 快慢双指针(Fast-Slow Pointers)三大黄金应用与数学证明¶
(1) 应用一:单链表中点定位(Finding Midpoint)¶
- 算法模型:
初始化慢指针
slow和快指针fast均指向链表起始位置。遍历过程中,slow每次前进一步(slow = slow->next),fast每次前进两步(fast = fast->next->next)。 - 奇偶长度数学推导: 设带头结点链表的数据结点数为 \(n\)。
- 奇数长度情况(设 \(n = 2m + 1\)):
当循环条件设定为
while (fast->next != NULL && fast->next->next != NULL)时,循环共执行 \(m\) 次。slow移动 \(m\)$ \text{步,最终停在第} $\(m + 1\) 个结点处,该结点恰好为正中间结点。 - 偶数长度情况(设 \(n = 2m\)):
若设定
while (fast != NULL && fast->next != NULL),slow停在第 \(m + 1\) 个结点(后半段的首结点); 若设定while (fast->next != NULL && fast->next->next != NULL),slow停在第 \(m\) 个结点(前半段的末尾结点)。在折半切断链表任务中,推荐后者,便于直接通过slow->next = NULL将链表平分为两截。
(2) 应用二:检索单链表倒数第 k 个结点(Offset Window)¶
- 算法模型: 双指针保持固定间距 \(k\) 进行滑动窗口遍历。
- 步骤证明:
- 指针 \(p\)$ \text{与} $\(q\) 均指向首元结点。
- 指针 \(p\)$ \text{沿链表先走} $\(k\)$ \text{步。若中途} $\(p == \text{NULL}\)$ \text{,说明链表长度不足} $\(k\),查找失败。
- 指针 \(p\)$ \text{与} $\(q\) 同步向后推进,步长均为 1。
- 当 \(p == \text{NULL}\)$ \text{时,} $\(p\)$ \text{相对于首元结点的偏移量为} $\(n\),\(q\)$ \text{相对于首元结点的偏移量为} $\(n - k\)$ \text{。此时指针} $\(q\)$ \text{所指结点即为倒数第} $\(k\)$ \text{个结点(序号为} $\(n - k + 1\))。 算法仅需单次遍历,时间复杂度 \(O(n)\)$ \text{,空间复杂度} $\(O(1)\)。
(3) 应用三:检测环路与定位环入口(Floyd 判圈算法)¶
-
环判定原理: 快指针速度为 2,慢指针速度为 1。若链表无环,快指针必定率先到达 \(\text{NULL}\);若链表存在环,两指针均进入环后,快指针相对慢指针的角速度为 1,离散距离每步缩减 1,因此在慢指针绕环不超过一整圈的时间内,快指针必追上慢指针并相遇。
-
环入口定位的数学推导: 设链表头结点到环入口结点的距离为 \(a\); 从环入口结点沿环行进到相遇结点的距离为 \(b\); 从相遇结点继续沿环行进到环入口结点的距离为 \(c\); 环的总周长为 \(L = b + c\)。
相遇时: * 慢指针移动的总步数: $\(S_{slow} = a + b\)$ * 快指针移动的总步数(设快指针在环内已绕行 \(k\)$ \text{圈,} $\(k \ge 1\)): $\(S_{fast} = a + kL + b\)$ * 依据运动学关系,快指针步数恒为慢指针的 2 倍: $\(S_{fast} = 2 S_{slow} \implies a + kL + b = 2(a + b)\)$ * 代数化简求解 \(a\): $$a = kL
-
b = (k
-
1)L + (L
-
b)$$ 因为 \(L = b + c\)$ \text{,所以} $\(L - b = c\),代入得: $\(a = (k - 1)L + c\)$
- 结论推导: 式中 \((k - 1)L\)$ \text{表示绕环整圈的距离,} $\(c\) 表示从相遇点继续沿环向前移动到环入口的距离。 若此时将一个指针重置到链表头结点,慢指针保留在相遇结点,两指针均以步长 1 同步向前移动: 当头指针走完距离 \(a\)$ \text{到达环入口时,慢指针恰好绕环走了} $\((k - 1)\)$ \text{圈并走完距离} $\(c\),亦到达环入口。 因此,两指针初次相遇的结点即为环入口结点。
5. 链表综合算法大题答题规范与边界防御机制¶
(1) 三段式答题规范结构¶
- 第一部分:算法基本设计思想 使用结构化自然语言分阶段列出算法策略(如“第一阶段:快慢指针定位中点并截断;第二阶段:三指针原地逆置后半段;第三阶段:双指针交叉归并”)。语言要求精炼严谨,避免口语化。
- 第二部分:C/C++ 语言算法描述 严格使用符合 C99 / C++ 规范的代码编写。核心逻辑必须带有注释。严禁使用未声明的第三方库函数,变量命名需具备语义。
- 第三部分:复杂度分析 分别明确给出时间复杂度与辅助空间复杂度,并写出推理依据(如“时间复杂度为 \(O(n)\)$ \text{,其中扫描中点耗时} $\(n/2\)$ \text{,逆置耗时} $\(n/2\)$ \text{,交织合并耗时} $\(n/2\)$ \text{,总耗时线性;算法仅引入常数个指针变量,辅助空间复杂度为} $\(O(1)\)”)。
(2) 必须防御的极端边界清单¶
- 空链表防御:
if (L == NULL || L->next == NULL) return; - 单元素与双元素链表防御:检查在 \(n=1\)$ \text{或} $\(n=2\) 时代码是否能够正确终止而不产生解引用空指针。
- 后半段断链防环防御:将链表截断时,必须显式将前半段末尾结点的指针置空(
slow->next = NULL;),否则会导致合并时形成死循环环路。 - 释放结点防野指针防御:
free(p); p = NULL;。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2024 年 408 第 1 题 · 单链表指针修改与头插功能分析¶
题目
已知带头结点的非空单链表 L 的头指针为 h,指针 p 指向 L 中间的一个链表结点(不是第一个和最后一个结点)。
执行语句:
A. 把 q 指向的结点插入到 p 的后面
B. 把 p 指向的结点插入到 q 的后面
C. 把 p 指向的结点插入到 h 的后面
D. 把 q 指向的结点插入到 h 的后面
【解析】¶
- 逐行状态追踪:
q = p->next;:指针变量 \(q\)$ \text{锁定结点} $\(p\) 的直接后继结点;p->next = q->next;:将结点 \(p\)$ \text{的后继指针跨越} $\(q\)$ \text{,直接指向} $\(q\)$ \text{的后继结点。此时结点} $\(q\)$ \text{已从原本的物理链接中被摘除,而} $\(p\)$ \text{与} $\(q\) 原后继重新接通;q->next = h->next;:结点 \(q\)$ \text{的后继指针指向当前链表的首元结点(即头结点} $\(h\) 的后继);h->next = q;:头结点 \(h\)$ \text{的后继指针指向结点} $\(q\)。- 逻辑效果汇总: 此四条语句先将结点 \(q\)$ \text{从其原始位置(} $\(p\)$ \text{的后继位置)剥离,随后通过标准的单链表头插法,将结点} $\(q\)$ \text{插入到头结点} $\(h\) 之后(作为新的首元结点)。
- 选项辨析:
- A 选项与 B 选项描述方向与执行结果相悖。
- C 选项错误,移动的物理实体是结点 \(q\)$ \text{,而非结点} $\(p\)。
- D 选项准确描述了将结点 \(q\)$ \text{插入到} $\(h\) 之后的完整行为。
正确答案:D
【真题 2】2023 年 408 第 2 题 · 双向链表插入指针时序依赖¶
题目
现有非空双向链表 L,结点结构为 prev | data | next。若要在 L 中指针 p 所指向的结点(非尾结点)之后插入指针 s 指向的新结点,在执行了语句序列:
A.
s->next->prev = p; s->prev = p;B.
p->next->prev = s; s->prev = p;C.
s->prev = s->next->prev; s->next->prev = s;D.
p->next->prev = s->prev; s->next->prev = p;
【解析】¶
- 现有执行状态分析: 双向链表中在 \(p\)$ \text{之后插入} $\(s\)$ \text{,设原后继结点为} $\(node_{next}\)$ \text{。初始状态下} $\(p\leftrightarrow node_{next}\)。 目标状态应为:\(p \leftrightarrow s \leftrightarrow node_{next}\)。 已执行的语句序列产生如下状态:
s->next = p->next;:此时 \(s\to next\)$ \text{正确指向} $\(node_{next}\);p->next = s;:此时 \(p\to next\)$ \text{已被覆盖为指向} $\(s\)。 尚欠缺的两条指针关系:- 关系一:\(s\to prev\)$ \text{应指向} $\(p\);
- 关系二:\(node_{next}\to prev\)$ \text{应指向} $\(s\)。
- 指针寻址障碍与选项逐项排查:
由于
p->next已经改变并指向 \(s\)$ \text{,表达式p->next->prev实际上等价于s->prev,已无法通过} $\(p\)$ \text{访问到原后继} $\(node_{next}\)$ \text{。原后继} $\(node_{next}\) 此时仅能通过s->next进行访问! - 排查 A 选项:
s->next->prev = p;使原后继的前驱指向了 \(p\)$ \text{,违背目标状态(应指向} $\(s\)),错误; - 排查 B 选项:
p->next为 \(s\),故p->next->prev = s;等价于s->prev = s;,形成自环,错误; - 排查 C 选项:
- 第一句
s->prev = s->next->prev;:由于原后继 \(node_{next}\)$ \text{的} $\(prev\)$ \text{尚未被改动,仍指向} $\(p\)$ \text{,因此该语句成功将} $\(s\to prev\)$ \text{赋值为} $\(p\); - 第二句
s->next->prev = s;:将原后继 \(node_{next}\)$ \text{的前驱指针更新为指向新结点} $\(s\)。 两句逻辑严密无误,完全恢复双向对称性!
- 第一句
- 排查 D 选项:赋值逻辑完全紊乱,错误。
正确答案:C
【真题 3】2021 年 408 第 1 题 · 循环单链表删除首元结点与单元素尾指针退化¶
题目
已知头指针 h 指向一个带头结点的非空单循环链表,p 是尾指针,q 是临时指针。现要删除该链表的第一个元素(首元结点),正确的语句序列是( )。
A. h->next = h->next->next; q = h->next; free(q);
B. q = h->next; h->next = h->next->next; free(q);
C. q = h->next; h->next = q->next; if (p != q) p = h; free(q);
D. q = h->next; h->next = q->next; if (p == q) p = h; free(q);
【解析】¶
- 删除首元结点基本流程:
- 首先用临时指针 \(q\) 备份首元结点地址:
q = h->next; - 头结点的后继指针跨过待删结点:
h->next = q->next; - 极端边界分析(单元素链表):
若该链表除头结点外仅包含 1 个数据结点,此时该结点既是首元结点,也是尾结点。
因此必有:
p == q(尾指针 \(p\)$ \text{与临时指针} $\(q\) 指向同一内存地址)。 在删除并释放 \(q\)$ \text{之后,原链表退化为空单循环链表。根据循环链表的拓扑定义,空链表的尾指针与头指针均必须指向头结点} $\(h\)(即满足p = h且h->next = h)。 若不进行if (p == q) p = h;更新,尾指针 \(p\)$ \text{依然保留原结点地址,但在执行free(q);之后,} $\(p\) 将沦为指向已释放堆内存的悬空指针(野指针),引发后续操作的未定义错误。 - 选项辨析:
- A 选项中先修改了
h->next,导致q = h->next取得的是第 2 个结点的地址,释放了错误的结点; - B 选项未考虑单元素链表导致的尾指针悬空问题;
- C 选项的判断条件
if (p != q)颠倒了逻辑分支; - D 选项正确兼顾了指针链接与边界尾指针的重置。
正确答案:D
【真题 4】2019 年 408 第 41 题 · 链表折半原地逆置与交叉合并综合算法¶
题目
设线性表 \(L = (a_1, a_2, a_3, \dots, a_{n-1}, a_n)\) 采用带头结点的单链表保存,链表结点结构为:
(1) 给出算法的基本设计思想;
(2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释;
(3) 说明你所设计算法的时间复杂度。
【标准答案与详尽推导】¶
(1) 算法基本设计思想¶
重排后的目标序列特点为:前半段序列 \((a_1, a_2, \dots)\)$ \text{与后半段逆序序列} $\((a_n, a_{n-1}, \dots)\)$ \text{依次交替穿插组合。为达到空间复杂度} $\(O(1)\),算法分为三个阶段:
1. 快慢指针折半定位并截断:
设置慢指针 slow 和快指针 fast,初值均指向头结点。遍历链表,slow 每次走 1 步,fast 每次走 2 步。当 fast 抵达末尾结点或其后继为 \(\text{NULL}\)$ \text{时,slow 恰好处于链表的前半段末尾。将链表从 slow 之后截断,前半段链表记为} $\(L_1\)$ \text{,后半段链表记为} $\(L_2\)。
2. 原地逆置后半段链表:
对后半段单链表 \(L_2\)$ \text{实施原地逆置(采用三指针滑动法或头插法),将其转化为} $\((a_n, a_{n-1}, \dots)\) 的逆序链表,整个过程不申请额外结点存储空间。
3. 双指针交替穿插归并:
设置两个工作指针分别指向 \(L_1\)$ \text{与逆置后的} $\(L_2\)$ \text{的首元结点,逐个将} $\(L_2\)$ \text{的结点插入到} $\(L_1\) 对应结点的后继位置,完成两路交错重排。
(2) 算法实现(C 语言描述)¶
void rearrange(NODE *h) {
/* 边界防御:空表、单结点或仅两结点无需重排 */
if (h == NULL || h->next == NULL || h->next->next == NULL) {
return;
}
/* 阶段一:快慢指针寻找链表中点并截断 */
NODE *slow = h;
NODE *fast = h;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next; /* 慢指针单步走 */
fast = fast->next->next; /* 快指针双步走 */
}
NODE *p2 = slow->next; /* p2 指向后半段的首元结点 */
slow->next = NULL; /* 关键边界:切断前半段链表,防环 */
/* 阶段二:原地翻转后半段链表(三指针滑动法) */
NODE *prev = NULL;
NODE *curr = p2;
while (curr != NULL) {
NODE *next_node = curr->next; /* 暂存后继 */
curr->next = prev; /* 指针反向 */
prev = curr; /* prev 右移 */
curr = next_node; /* curr 右移 */
}
p2 = prev; /* p2 重新指向逆置后半段的头结点 */
/* 阶段三:将前半段与逆置后的后半段交替穿插合并 */
NODE *p1 = h->next; /* p1 指向前半段首元结点 */
while (p1 != NULL && p2 != NULL) {
NODE *q1 = p1->next; /* 暂存 p1 的原后继 */
NODE *q2 = p2->next; /* 暂存 p2 的原后继 */
p1->next = p2; /* 将 p2 插入 p1 之后 */
p2->next = q1; /* 将原后继 q1 接在 p2 之后 */
p1 = q1; /* 推进 p1 指针 */
p2 = q2; /* 推进 p2 指针 */
}
}
(3) 复杂度分析¶
- 时间复杂度:
- 快慢指针折半扫描:遍历前半程耗时 \(\approx n/2\);
- 原地逆置后半段:遍历后半程耗时 \(\approx n/2\);
- 两路交错合并:遍历合并耗时 \(\approx n/2\)。 各阶段均为线性扫描,总时间复杂度为 \(O(n)\)。
- 辅助空间复杂度:
算法中仅定义了若干辅助指针变量(
slow,fast,p1,p2,prev,curr等),并未申请任何动态内存分配空间,辅助空间复杂度为 \(O(1)\)。
【真题 5】2016 年 408 第 1 题 · 单链表内存物理地址映射与链接地址分析¶
题目
已知表头元素为 c 的单链表在内存中的存储状态如下表所示。
现将 f 存放于 1014H 处并插入单链表,若 f 在逻辑上位于 a 和 e 之间,则 a, e, f 的“链接地址”依次是( )。
| 内存地址 | 1000H | 1004H | 1008H | 100CH | 1010H | 1014H |
|---|---|---|---|---|---|---|
| 元素数据 | c | b | a | d | e | f |
| 链接地址 | 1008H | 100CH | 1010H | NULL | 1004H | ? |
A. 1010H, 1014H, 1004H
B. 1010H, 1004H, 1014H
C. 1014H, 1010H, 1004H
D. 1014H, 1004H, 1010H
【解析】¶
- 单链表“链接地址”概念: 单链表中结点的“链接地址”即为其指针域 \(next\) 存储的后继结点的物理内存基地址。
- 反推初始链表逻辑拓扑: 从表头结点 c 开始沿链追踪:
- c 存放于 1000H,链接地址为 1008H(对应元素 a);
- a 存放于 1008H,链接地址为 1010H(对应元素 e);
- e 存放于 1010H,链接地址为 1004H(对应元素 b);
- b 存放于 1004H,链接地址为 100CH(对应元素 d);
- d 存放于 100CH,链接地址为 \(\text{NULL}\)(尾结点)。 逻辑序列为:\(c \to a \to e \to b \to d\)。
- 插入新元素 f 后的拓扑变更: 将存放在 1014H 的元素 f 插入在 a 和 e 之间: 逻辑序列变为:\(c \to a \to f \to e \to b \to d\)。
- 结点 a 的后继由 e 变为 f,因此 a 的链接地址应更新为 f 的存储地址 1014H;
- 结点 f 的后继为 e,因此 f 的链接地址应设置为 e 的存储地址 1010H;
- 结点 e 的后继依然为 b,其链接地址保持原值不变,仍为 1004H。
- 校验所求顺序: 题目要求给出 a, e, f 的链接地址:
- a 的链接地址:1014H;
- e 的链接地址:1004H;
- f 的链接地址:1010H。 依次为 1014H, 1004H, 1010H。
正确答案:D
【真题 6】2016 年 408 第 2 题 · 双向循环链表结点删除操作¶
题目
已知一个带有表头结点的双向循环链表 L,结点结构为 prev | data | next。现要删除指针 p 所指的结点,正确的语句序列是( )。
A. p->next->prev = p->prev; p->prev->next = p->prev; free(p);
B. p->next->prev = p->next; p->prev->next = p->next; free(p);
C. p->next->prev = p->next; p->prev->next = p->prev; free(p);
D. p->next->prev = p->prev; p->prev->next = p->next; free(p);
【解析】¶
- 双向循环链表删除逻辑: 删除结点 \(p\)$ \text{需要将} $\(p\) 的直接前驱与直接后继重新建立直接的双向链接:
- \(p\)$ \text{的后继结点的} $\(prev\)$ \text{指针绕过} $\(p\)$ \text{,指向} $\(p\) 的前驱结点:
p->next->prev = p->prev; - \(p\)$ \text{的前驱结点的} $\(next\)$ \text{指针绕过} $\(p\)$ \text{,指向} $\(p\) 的后继结点:
p->prev->next = p->next; - 释放结点 \(p\) 所占用的堆内存空间:
free(p); - 选项逐项核验:
- A 选项第二句中将
p->prev->next指向了p->prev,导致前驱的后继指针指向自身形成死循环; - B 选项第一句中将
p->next->prev指向了p->next,产生自环; - C 选项两句修改均发生自环错误;
- D 选项两句完全正确实现了前驱与后继的相互跳跃式跨接。
正确答案:D
四、 核心解题套路与易错陷阱¶
1. 选择题秒杀套路:拓扑时序依赖判定法¶
在判断多行指针赋值代码的正确性时,推荐遵循三步走校验法:
1. 查暂存:检查是否有关键结点的地址未被额外指针备份,就作为左值被直接覆盖(如 p->next = s; 是否发生在需要用 p->next 索引其他结点之前);
2. 查对称:对于双向链表,插入或删除后必须成对检查 \(A\to next = B\)$ \text{与} $\(B\to prev = A\) 是否均已完成维护;
3. 查自环:警惕类似 p->next->prev = p->next 或 p->next = p 形式的自环错误语句。
2. 算法大题三段式模板化组合策略¶
408 链表算法大题通常由以下基础模块拼装而成:
* 模块 1:快慢指针中点切断
牢记循环终止条件 while (fast->next != NULL && fast->next->next != NULL),慢指针刚好位于前半段尾部,随后执行 slow->next = NULL;。
* 模块 2:三指针原地翻转
利用 prev, curr, next_node 模板,4 行核心代码实现 \(O(1)\) 空间逆置。
* 模块 3:双路归并或交织穿插
暂存两指针原后继,按特定规则交错挂接。
3. 常见命题陷阱与边界死穴¶
- 死穴 1:循环链表判空与循环终止条件误用
在普通单链表中循环终止条件为
p != NULL,但在循环链表中遍历终止条件为p != head或p->next != head。误写为NULL将直接造成死循环。 - 死穴 2:单元素单向循环链表删除后未更新尾指针
当循环链表只有一个元素被删除后,链表变成空循环链表,此时尾指针 \(p\)$ \text{必须重置为指向头结点} $\(h\)(即
p = h)。 - 死穴 3:拆分链表未显式截断 对链表做拆分或折半处理时,若未将前半段尾结点的 \(next\)$ \text{指针赋值为} $\(\text{NULL}\),后续遍历或合并操作将进入环路。
- 死穴 4:解引用空指针防御缺失
在执行
fast->next->next之前,必须严格先行判断fast->next != NULL,严防段错误(Segmentation Fault)。
五、 考点速记清单¶
- 结构判空条件:
- 带头单链表:
head->next == NULL - 带头双向链表:
head->next == NULL - 带头循环单链表:
head->next == head - 带头循环双链表:
head->next == head且head->prev == head - 单链表后插时序:先连后
s->next = p->next;,再连前p->next = s;。 - 单链表前插转换:转化为后插后,交换两结点数据域即可在 \(O(1)\) 时间内达成前插效果。
- 双向循环链表删除指定结点 \(p\): $\(p\to next\to prev = p\to prev;\)$ $\(p\to prev\to next = p\to next;\)$ $\(free(p);\)$
- 快慢指针折半准则:
fast步长为 2,slow步长为 1。奇数个结点停在正中,偶数个结点停在前半段末尾(条件设为fast->next != NULL && fast->next->next != NULL)。 - Floyd 环入口定理:两指针在环内相遇后,一指针回表头,另一指针留相遇点,均以步长 1 前进,两指针初次相遇处即为环入口。
- 大题代码防御三必须:
- 必须校验输入链表是否为空或长度为 1;
- 必须在切分链表后显式置
tail->next = NULL; - 必须写明时间复杂度 \(O(n)\)$ \text{与辅助空间复杂度} $\(O(1)\)。