目标

追踪单链表的链接变化，识别头结点、指针更新顺序和定位成本。

前置知识

建议先掌握单链表结点结构、头指针与头结点，以及已知前驱时的插删操作。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔或一份错题记录。
• 输入：本页按源文件顺序整理的 10 道选择题。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击“提交答案”，再核对对错、正确答案和题解；
3. 做错的题点击“重新作答”后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再展开组件生成的答案总览，避免只记答案字母。

选择题

答题进度已答 0/10正确 0

第 1 题

难度★★考点单链表、合并、时间复杂度标识ds-2013-01

已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是()。

请选择一个答案

AO(n)

BO(m×n)

CO(min(m,n))

DO(max(m,n))

第 2 题

难度★★★考点单链表、链式存储、插入操作、链接地址标识ds-2016-01

已知表头元素为 c 的单链表在内存中的存储状态如下表所示。现将 f 存放于 1014H 处并插入单链表，若 f 在逻辑上位于 a 和 e 之间，则 a, e, f 的"链接地址"依次是( )。

结构（文字版）：表中每行给出"地址 / 元素 / 链接地址"。

地址	元素	链接地址
1000H	a	1010H
1004H	b	100CH
1008H	c	1000H
100CH	d	NULL
1010H	e	1004H
1014H	（空）	（空）

表头元素是 c（位于 1008H）。1014H 是新结点 f 的预留位置。

请选择一个答案

A1010H, 1014H, 1004H

B1010H, 1004H, 1014H

C1014H, 1010H, 1004H

D1014H, 1004H, 1010H

第 3 题

难度★★★考点单链表、指针操作、结点插入标识ds-2024-01

已知带头结点的非空单链表 L 的头指针为 h，指针 p 指向 L 中间的一个链表结点(不是第一个和最后一个结点)。q=p->next，p->next=q->next，q->next=h->next，h->next=q。这段代码的功能是()。

请选择一个答案

A把 q 指向的结点插入到 p 的后面

B把 p 指向的结点插入到 q 的后面

C把 p 指向的结点插入到 h 的后面

D把 q 指向的结点插入到 h 的后面

第 4 题

难度★★考点单链表、头指针、头结点、基本概念标识ds-drill-singly-linked-list-001

下列关于单链表中"头指针"与"头结点"的说法中，错误的是( )。

请选择一个答案

A头指针是一个指针变量，存放链表第一个结点的内存地址（带头结点的链表中，指向头结点）

B头结点是带头结点单链表中的第一个结点，但不存放实际数据元素，其 next 指向第一个真正的数据结点

C头指针为 NULL 表示空链表；带头结点时也可用"头结点的 next 为 NULL"表示空链表

D不带头结点的单链表不需要头指针，只要靠首结点的 next 字段就能定位整个链表

第 5 题

难度★★★考点单链表、头结点、表头插入、操作统一性标识ds-drill-singly-linked-list-002

在不带头结点与带头结点的两种单链表上实现"在表头插入一个新结点 $s$"的操作，下列说法正确的是( )。

请选择一个答案

A两种链表的实现代码完全相同

B不带头结点时需要特判"修改头指针 $L$ 本身"，带头结点时不需要

C带头结点时需要特判"修改头指针 $L$ 本身"，不带头结点时不需要

D两种链表都需要遍历到表尾才能完成表头插入

第 6 题

难度★★★考点单链表、插入操作、指针顺序标识ds-drill-singly-linked-list-003

在带头结点的单链表中，已知指针 $p$ 指向某非尾结点。要在 $p$ 之后插入指针 $s$ 所指向的新结点，下列语句序列中正确的是( )。

请选择一个答案

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

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

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

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

第 7 题

难度★★★★考点单链表、删除操作、O(1)删除技巧标识ds-drill-singly-linked-list-004

设带头结点的单链表中，指针 $p$ 指向某非尾结点（即 $p->\text{next}\ne \text{NULL}$）。只给定 $p$、不知道其前驱的情况下，要以 $O(1)$ 时间"逻辑删除" $p$ 所指结点（即让链表"看起来" $p$ 不存在）的下列方法中，正确的是( )。

请选择一个答案

Ap->next = p->next->next;

Bq = p->next; p->data = q->data; p->next = q->next; free(q);

Cfree(p); p = p->next;

D无法做到 $O(1)$ 时间删除——单链表无前驱指针，必须从头遍历找到 $p$ 的前驱再改其 next，时间 $O(n)$

第 8 题

难度★★★考点单链表、倒数第k个、双指针标识ds-drill-singly-linked-list-005

在带头结点的单链表中，要找到倒数第 $k$ 个结点（$k\ge 1$，假设链表长度 $n\ge k$），下列方法中时间和空间都最优的是( )。

请选择一个答案

A先遍历一遍得到链表长度 $n$，再从头遍历到第 $n-k+1$ 个结点

B用两个指针 $p$、$q$ 同时从头结点出发，$p$ 先走 $k$ 步，然后 $p$、$q$ 同步前进，$p$ 走过尾结点变为 $\text{NULL}$ 时 $q$ 指向倒数第 $k$ 个结点

C用递归到达链表尾部时返回，回溯过程中计数到 $k$ 时返回当前结点

D从链表尾部向前遍历 $k$ 步（单链表不支持反向遍历，需先逆置）

第 9 题

难度★★★★考点单链表、原地逆置、头插法标识ds-drill-singly-linked-list-006

对带头结点的单链表 $L$：

list L: 1, 2, 3, 4

执行下列代码后，$L$ 的内容（从首元结点到末元结点）是( )。

ListNode *p = L->next, *q;
L->next = NULL;
while (p) {
    q = p->next;
    p->next = L->next;
    L->next = p;
    p = q;
}

请选择一个答案

A$1\to 2\to 3\to 4$（链表内容不变）

B$4\to 3\to 2\to 1$

C$4\to 1\to 2\to 3$

D$2\to 1\to 4\to 3$

第 10 题

难度★★★★考点单链表、公共结点、双指针、共享后缀标识ds-drill-singly-linked-list-007

设两个带头结点的单链表 $L_A$、$L_B$ 的长度分别为 $m$、$n$（不含头结点），且存在共同后缀——即从某一结点 $P$ 开始，两条链表共享所有后续结点（物理上是同一段存储）。要找出共同后缀的起始结点 $P$，下列算法中时间和空间都最优的是( )。

请选择一个答案

A对 $L_A$ 的每个结点，都拿去和 $L_B$ 的所有结点逐一比较指针（外层扫 $L_A$、内层扫 $L_B$），发现指针相等即为 $P$

B把 $L_A$ 所有结点指针放入哈希表，再扫描 $L_B$ 找第一个在哈希表中存在的结点指针

C让较长链表的指针先走 $|m-n|$ 步，然后两指针同步前进直到相遇（即指针相等）

D把两条链表都逆置后扫描相同前缀

答案总览（建议完成全部题目后查看）

1. 第 1 题：D
2. 第 2 题：D
3. 第 3 题：D
4. 第 4 题：D
5. 第 5 题：B
6. 第 6 题：C
7. 第 7 题：B
8. 第 8 题：B
9. 第 9 题：B
10. 第 10 题：C

完成清单

• 10 道题均在展开答案前独立作答；
• 每道错题都记录了错误原因，而不只抄写正确答案；
• 能说明至少两道指针或复杂度题的完整推理过程；
• 复做错题时能够在不看解析的情况下得到正确结论。

思考题

1. 头结点为什么能统一表头插入和删除的边界？
2. 为什么在 p 后插入 s 时必须先保存 p 的原后继？
3. 链表的局部修改是 O(1) 时，整体操作为什么仍可能是 O(n)？

复盘

• 我最容易在哪个前提上出错：结构类型、是否带头结点、是否循环、还是是否已知目标节点？
• 我是否能画出链接变化或写出移动次数，而不是只凭关键词选择？
• 哪道题的错误选项最有迷惑性？它利用了哪个常见概念混淆？