第2章线性表

2027 王道 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第2章线性表¶

⚠️ 线性表是算法题命题的重点。要牢固掌握顺序存储与链式存储下的各种基本操作，注重动手能力。 💡 教材的应试提醒：算法最重要的是思想，考场上不要求代码可执行，重点是清晰表达核心思想与关键步骤，不必拘泥语法边界；即使暴力法通常也能拿大部分分。⚠️ 算法题只能用 C/C++ 实现。

回源 · PDF 第 25 页 · b_25_5

【知识树】第2章骨架¶

线性表的定义与基本操作（九个操作）
顺序表
静态分配 / 动态分配
插入、删除、按值查找及其平均移动次数
链表
单链表：头指针 vs 头结点、初始化/求表长/查找/插入/删除
头插法与尾插法
双链表、循环链表（循环单链表 / 循环双链表）
静态链表
顺序表与链表的对比与选型

回源 · PDF 第 25 页 · b_25_0；PDF 第 25 页 · b_25_2

2.1 线性表的定义和基本操作¶

线性表的定义和五个特点？¶

线性表是由 n（n ≥ 0）个相同数据类型的元素组成的有限序列，n 为表长，n = 0 时为空表。 - a₁ 是唯一的表头元素，aₙ 是唯一的表尾元素 - ⚠️ 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

五个特点： - 元素个数有限 - 元素有逻辑上的顺序性（存在明确先后次序） - 每个元素被视为一个不可分割的单位 - ⚠️ 数据类型都相同 → 每个元素占有相同大小的存储空间 - 具有抽象性：只讨论元素之间的逻辑关系，不考虑其表示什么内容

⚠️ 最容易混的一句：线性表是逻辑结构；顺序表和链表是存储结构，属于不同层面的概念。

回源 · PDF 第 25 页 · b_25_7；PDF 第 25 页 · b_25_8

线性表的九个基本操作？¶

InitList(&L) 初始化 / DestroyList(&L) 销毁
Length(L) 求表长 / Empty(L) 判空 / PrintList(L) 输出
LocateElem(L, e) 按值查找，返回其位置
GetElem(L, i) 按位查找，获取第 i 个位置的元素值
ListInsert(&L, i, e) 在第 i 个位置插入 e
ListDelete(&L, i, &e) 删除第 i 个元素，用 e 返回被删元素的值

⚠️ 两点说明：基本操作的具体实现取决于所用的存储结构；符号 & 是 C++ 的引用调用，C 语言中用指针实现相同效果。

回源 · PDF 第 26 页 · b_26_3

2.2 线性表的顺序表示¶

顺序表为什么能随机存取？　★5考¶

顺序表用一组地址连续的存储单元依次存储元素，使逻辑上相邻的元素在物理位置上也相邻。

⚠️ 随机存取的根据：任意元素的存储地址与起始地址之间的偏移量与其位序呈线性关系 → 可在 O(1) 时间内直接访问任意位置的元素。

⚠️ 位序从 1 开始，数组下标从 0 开始 —— 做题时注意转换。

★ 考过 2010、2011、2018、2020、2025

回源 · PDF 第 27 页 · b_27_8

静态分配和动态分配差在哪？动态分配算链式吗？¶

静态分配：ElemType data[MaxSize]; int length; —— ⚠️ 数组大小和存储空间在编译时已固定，占满后再插入会溢出
动态分配：ElemType *data; int MaxSize, length; —— 运行时申请，占满后另开一块更大的空间，把原表元素复制过去
C：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
C++：L.data = new ElemType[InitSize];

⚠️ 高频陷阱：动态分配不是链式存储，它仍然是顺序存储 —— 物理结构没变，依然支持随机存取，只是容量可在运行时调整。

回源 · PDF 第 28 页 · b_28_5

顺序表的两优两缺？¶

优点： - 可随机访问，由首地址 + 元素序号在 O(1) 内定位 - ⚠️ 存储密度高：每个结点仅存数据元素，无额外指针开销

缺点： - 插入和删除效率低，需要移动大量元素 - 要求连续的存储空间，不够灵活

回源 · PDF 第 28 页 · b_28_6

顺序表插入的三种情况和平均移动次数？　★1考¶

合法插入位置是 1 ≤ i ≤ L.length + 1；把第 i 个元素及其后所有元素依次后移一位。

最好：表尾插入（i = n+1），不移动 → O(1)
最坏：表头插入（i = 1），移动全部 n 个 → O(n)
平均：pᵢ = 1/(n+1)，平均移动 ∑ pᵢ(n−i+1) = n/2 → O(n)

⚠️ 代码里最容易问的一处：判断合法性用 length+1，移动元素的 for 循环用 length —— 因为合法插入位置包括第 n+1 位，但移动元素最多从第 n 位开始后移。

★ 考过 2023

回源 · PDF 第 28 页 · b_28_8

顺序表删除的平均移动次数？¶

合法范围 1 ≤ i ≤ L.length；把第 i 个位置之后的元素前移一位。 - 最好：删表尾（i = n） → O(1) - 最坏：删表头（i = 1），移动 n−1 个 → O(n) - 平均：pᵢ = 1/n，平均移动 ∑ pᵢ(n−i) = (n−1)/2 → O(n)

💡 一起记：插入平均 n/2，删除平均 (n−1)/2 —— 插入比删除多挪半个。 ⚠️ 共同结论：顺序表插入删除的时间开销主要耗费在移动元素上，移动个数取决于操作位置。

回源 · PDF 第 29 页 · b_29_12

顺序表按值查找与按位查找的复杂度为什么不同？¶

按值查找（顺序查找）：从表头开始逐个比较，返回第一个值等于 e 的元素的位序；找不到返回 0。

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; ++i)
        if (L.data[i] == e) return i + 1;   // 数组下标 i 对应位序 i+1
    return 0;
}

最好：目标在表头，只比较 1 次 → O(1)
最坏：目标在表尾或不存在，比较 n 次 → O(n)
等概率成功查找的平均比较次数：\(\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}\) → O(n)

⚠️ 按位查找可由数组下标直接定位，是 O(1)；按值查找不知道目标位置，只能顺序比较，是 O(n)。不要把“顺序表支持随机存取”误解成“按值也能 O(1) 查到”。

回源 · PDF 第 30 页 · b_30_4；PDF 第 30 页 · b_30_5；PDF 第 30 页 · b_30_6；PDF 第 30 页 · b_30_7；PDF 第 30 页 · b_30_8；PDF 第 30 页 · b_30_9；PDF 第 30 页 · b_30_10；PDF 第 30 页 · b_30_11；PDF 第 30 页 · b_30_12

2.3 线性表的链式表示¶

链式存储用什么换来了什么？¶

放弃的：⚠️ 失去随机存取能力，只能从头开始顺序访问；每个结点额外存一个指针，有存储开销。 换来的：不要求地址连续；插入删除无须移动元素，只需修改指针。

单链表结点结构：data（数据域）+ next（指针域）

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

回源 · PDF 第 42 页 · b_42_9

头指针和头结点是一回事吗？　★1考¶

⚠️ 不是。 - 头指针：⚠️ 始终指向链表的第一个结点（无论带不带头结点）；头指针为 NULL 表示链表为空 - 头结点：⚠️ 只存在于带头结点的链表中，是链表的第一个结点，数据域一般不存放有效数据（但可用于记录表长）

带头结点：头指针 L → 头结点 → 第一个数据结点
不带头结点：头指针 L → 直接指向第一个数据结点
⚠️ 两种形式表尾结点的指针域都为 NULL

★ 考过 2009、2012、2013、2015、2016、2019

回源 · PDF 第 43 页 · b_43_1

引入头结点的两个好处？¶

操作统一性：⚠️ 第一个数据结点的位置存在头结点的指针域中 → 在链表首部插入删除时与其他位置逻辑一致，无须特殊处理
空表与非空表处理统一：⚠️ 头指针始终非空（指向头结点），空表仅表现为头结点的 next 为 NULL → 避免了对空表的单独判断

💡 这就是为什么教材说"带头结点的单链表在操作实现上更为简便"，后续算法默认带头结点。

回源 · PDF 第 43 页 · b_43_12

单链表求表长、按序号查找、按值查找的复杂度？¶

三个都是 O(n)。 - 求表长：⚠️ 统计的是数据结点个数，不包括头结点；从第一个数据结点起遍历计数 - 按序号查找 GetElem：j 记录当前位序，头结点是第 0 个结点，循环到第 i 个；i 超出表长返回 NULL - 按值查找 LocateElem：从第一个数据结点起逐个比较数据域

💡 指针语法要点：p->data 与 (*p).data 完全等价；成员运算符 . 左侧是结构体变量，指向运算符 -> 左侧是结构体指针；p->next->data 等价于 (*(*p).next).data。

回源 · PDF 第 44 页 · b_44_7；PDF 第 44 页 · b_44_10

单链表插入的两步为什么不能颠倒？　★2考¶

在第 i−1 个结点 *p 后插入 *s：

s->next = p->next;   // ①
p->next = s;         // ②

⚠️ 顺序不可颠倒：若先执行 p->next = s，原后继地址就丢了，导致 s->next = p->next 实际变成 s->next = s，形成自环。

复杂度：O(n)，主要开销在查找前驱结点；⚠️ 若已知某结点指针，在其后插入是 O(1)。 ⚠️ i = 1 时：不带头结点的要更新头指针 L，带头结点的无须特殊处理。

★ 考过 2016、2024

回源 · PDF 第 45 页 · b_45_3

前插操作怎么做到 O(1)？¶

常规做法：从头结点顺序查找其前驱，转化为后插 → O(n)

O(1) 技巧（⚠️ 适用于数据可复制的情况）：把新结点 *s 插到目标结点 *p 之后，再交换 *p 与 *s 的数据域

s->next = p->next;   // 修改指针域，不能颠倒
p->next = s;
temp = p->data;      // 交换数据域
p->data = s->data;
s->data = temp;

💡 本质：逻辑上等效于前插，物理上是后插 + 换数据。

回源 · PDF 第 45 页 · b_45_9；PDF 第 45 页 · b_45_10

删除给定结点 *p 怎么做到 O(1)？它有什么局限？¶

常规：从头遍历找 *p 的前驱 → O(n)

O(1) 技巧：把 *p 的后继结点的数据复制到 *p 中，然后删除其后继结点

LNode *q = p->next;
p->data = p->next->data;   // 用后继的数据覆盖
p->next = q->next;
free(q);

⚠️ 局限：不能用于删除尾结点（因其无后继）。

常规删除（删第 i 个）：找到第 i−1 个结点 *p，令 p->next = q->next 再 free(q)，复杂度 O(n)，主要耗时在查找。 ⚠️ 不带头结点时要判断被删结点是否为首结点并特殊处理头指针；带头结点时删首结点与删其他结点操作相同。

回源 · PDF 第 46 页 · b_46_6

头插法建立的链表为什么是逆序的？¶

做法：从空表开始，每次生成新结点 *s，令 s->next 指向头结点当前 next 所指的结点，再让头结点的 next 指向 *s。

⚠️ 新结点始终成为第一个数据结点 → 最终链表中元素顺序与输入顺序相反。

💡 所以头插法又叫"逆向建立单链表"，考试里常用它来实现链表逆置。

回源 · PDF 第 46 页 · b_46_9；PDF 第 46 页 · b_46_12

尾插法为什么要设尾指针 r？¶

希望输入顺序与链表元素顺序一致时用尾插法：维护尾指针 r 始终指向当前尾结点，插入时 r->next = s; r = s;，⚠️ 最后要执行 r->next = NULL 把尾结点指针置空。

⚠️ 因为附设了尾指针，无须遍历查找尾部，总时间复杂度仍为 O(n)（头插法也是 O(n)，每次插入 O(1)）。

💡 头插法若不带头结点，主要修改点是：每次插入新结点后都要把它的地址赋给头指针 L。

回源 · PDF 第 47 页 · b_47_4；PDF 第 47 页 · b_47_7

2.3.3 双链表¶

引入双链表解决了什么问题？¶

⚠️ 单链表的局限：只能从前往后遍历，要访问某结点的前驱必须从头遍历，O(n)。

双链表每个结点有两个指针：prior（直接前驱）和 next（直接后继）；⚠️ 头结点的 prior 为 NULL，尾结点的 next 为 NULL。

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

⚠️ 按值查找和按位查找与单链表相同，仍需从头顺序查找；⚠️ 但在已知目标结点的前提下，插入和删除可降至 O(1)。

回源 · PDF 第 48 页 · b_48_2；PDF 第 48 页 · b_48_3

双链表插入的四步顺序有什么约束？　★1考¶

在结点 *p 之后插入 *s：

① s->next = p->next;
② p->next->prior = s;
③ s->prior = p;
④ p->next = s;

⚠️ ①必须在④之前 —— 否则 p->next 被覆盖后无法访问原后继，指针丢失，插入失败。其余步骤可在保证逻辑正确的前提下适当调整（例如③可在①前执行）。

💡 通用心法：先接新结点的两端，再断开旧连接。

★ 考过 2023

回源 · PDF 第 48 页 · b_48_11

双链表删除的两步？　★1考¶

删除 *p 的后继结点 *q：

p->next = q->next;      // ①
q->next->prior = p;     // ②
free(q);

⚠️ 关键在于两个方向的链接都要修好，不能造成断链。

★ 考过 2016

回源 · PDF 第 49 页 · b_49_1

2.3.4 循环链表¶

循环单链表的判空条件是什么？　★1考¶

⚠️ 尾结点的 next 指向头结点，链表中不存在 next 为 NULL 的结点。

判空条件不再是头指针 L 是否为空，而是 L->next == L（头结点的 next 指向自身）。

优点：从任意一个结点出发都能遍历整个链表。 ⚠️ 因为是个环，在任何位置上的插入和删除都是等价的，无须判断是否到达表尾。

★ 考过 2021

回源 · PDF 第 49 页 · b_49_14

循环单链表为什么常用尾指针而不用头指针？¶

⚠️ 只设尾指针 r 时，表头和表尾插入都是 O(1)；若用头指针，表尾插入要遍历整个链表，O(n)。

表尾插入 *s 的三步： - s->next = r->next（新结点后继指向头结点，维持环状） - r->next = s - r = s（更新尾指针）

💡 记忆法："尾指针一手抓两头" —— r 是尾，r->next 就是头。

回源 · PDF 第 49 页 · b_49_16

循环双链表空表时是什么状态？¶

设尾结点为 *p，则 p->next 指向头结点 L，同时 L->prior 指向 *p
⚠️ 空表时头结点 L 的 prior 和 next 都指向自身：L->prior == L 且 L->next == L

回源 · PDF 第 50 页 · b_50_2；PDF 第 50 页 · b_50_3

2.3.5 静态链表¶

静态链表的"指针"是什么？结束标志是什么？¶

静态链表用数组模拟链式存储：每个结点含 data 域和 next 域，⚠️ 这里的 next 不是真指针，而是结点在数组中的相对地址（数组下标），也称游标。

/**/ #define MaxSize 50
typedef struct{
    ElemType data;
    int next;          // 下一个元素的数组下标
} SLinkList[MaxSize];

⚠️ 结束标志是 next == −1（不是 NULL）。 ⚠️ 和顺序表一样需要预先分配一块连续的内存空间。

插入删除同样只改"指针"（下标），无须移动元素；⚠️ 它的价值在于在不支持指针的语言（如 Basic）中提供了链式方案。

回源 · PDF 第 50 页 · b_50_4；PDF 第 50 页 · b_50_5

2.3.6 顺序表和链表的比较¶

顺序表 vs 链表的四维对照？¶

维度	顺序表	链表
存取方式	⚠️ 随机存取 O(1)，也支持顺序存取	⚠️ 只支持顺序存取，访问第 i 个平均 O(n)
逻辑与物理	逻辑相邻则物理连续，邻接关系由地址体现	物理未必相邻，逻辑关系由指针显式维护
查找	无序 O(n)；⚠️ 有序可折半查找 O(log₂n)；按序号 O(1)	无序 O(n)；按序号 O(n)
插入删除	⚠️ 平均移动约一半元素，开销大	⚠️ 只改指针不移动元素，但前提是已知位置（否则仍需 O(n) 定位）

⚠️ 空间分配：顺序表静态分配过大浪费、过小溢出；动态分配要申请新连续块并复制全部数据，耗时且可能因缺乏连续空闲空间而失败。链表按需扩展灵活性高，但⚠️ 存储密度小于 1。

回源 · PDF 第 50 页 · b_50_11

实际怎么选存储结构？（三个考虑）¶

基于存储：⚠️ 长度或规模难以预估时顺序表不适用（要预分配固定容量），链表可按需扩展但每结点多存指针
基于运算：⚠️ 频繁按序号访问选顺序表（O(1)）；以插入删除为主选链表 —— 尽管定位仍需 O(n)，但增删密集场景下链表整体性能通常更优
基于环境：顺序表基于数组，几乎所有语言都支持、实现简单；链表依赖指针操作，在部分环境中实现较复杂

💡 一句话结论：规模稳定、以随机访问为主 → 顺序存储；动态性强、频繁增删 → 链式存储。

回源 · PDF 第 51 页 · b_51_4

【原书试题精选与答案方法】第2章¶

怎样在线性时间内删除顺序表的唯一最小值，并用表尾元素补空位？（2.2 综合应用题 01）¶

扫描一遍顺序表，用 value 记录当前最小值、pos 记录其下标；扫描结束后执行 L.data[pos]=L.data[L.length-1]，再令表长减 1。

时间复杂度：\(O(n)\)。
额外空间：\(O(1)\)。
这道题不要求保持原相对次序，所以可用表尾元素直接覆盖，避免整体前移。
空表必须先报错或返回失败；被删最小值通过引用参数返回。

⚠️ 若题目要求保持次序，就不能使用“表尾补洞”。

回源 · PDF 第 34 页 · b_34_18；PDF 第 34 页 · b_34_19；PDF 第 34 页 · b_34_21；PDF 第 35 页 · b_35_0

顺序表原地逆置为什么只需扫描前一半？（2.2 综合应用题 02）¶

令下标 \(i\) 从 0 到 length/2-1，每次交换 L.data[i] 与 L.data[length-i-1]。

每对对称元素只交换一次；中间元素（奇数长度时）无需处理。
时间复杂度 \(O(n)\)，额外空间 \(O(1)\)。

💡 逆置的核心不是“搬到新数组”，而是左右对称交换。

回源 · PDF 第 35 页 · b_35_3；PDF 第 35 页 · b_35_4；PDF 第 35 页 · b_35_6

删除顺序表中所有满足条件的元素，怎样做到稳定、原地且只扫一遍？（2.2 综合应用题 03、04）¶

两题都用稳定压缩：顺序扫描，只把“应保留”的元素写到前面的连续位置。

方法一：k 记录已保留元素个数，保留时写入 data[k++]。
方法二：k 记录已删除元素个数，保留时前移到 data[i-k]。
Q03 的删除条件是 data[i]==x；Q04 只需改成 s<=data[i]&&data[i]<=t，并先检查空表及 s<t。
时间 \(O(n)\)、空间 \(O(1)\)，且保留元素的相对顺序不变。

⚠️ 从两端用右端元素补洞也可做到线性，但会改变相对次序；题目若隐含“稳定”要求，应选压缩法。

回源 · PDF 第 35 页 · b_35_7；PDF 第 35 页 · b_35_8；PDF 第 35 页 · b_35_11；PDF 第 36 页 · b_36_1；PDF 第 36 页 · b_36_2；PDF 第 36 页 · b_36_6

有序顺序表去重为什么只需比较“最后一个已保留元素”？（2.2 综合应用题 05）¶

有序表的重复值必然连续。令 i 指向去重后区域的最后一个元素，j 扫描原表：若 data[j]!=data[i]，就执行 data[++i]=data[j]；最后令 length=i+1。

时间 \(O(n)\)，空间 \(O(1)\)。
无序表不能直接用相邻比较；教材提示可用散列表做到期望 \(O(n)\)，代价是额外空间。

💡 i 管“答案尾”，j 管“扫描头”。

回源 · PDF 第 36 页 · b_36_7；PDF 第 36 页 · b_36_8；PDF 第 36 页 · b_36_10；PDF 第 36 页 · b_36_12；PDF 第 36 页 · b_36_13

两个递增顺序表怎样合并成新的有序表？（2.2 综合应用题 06）¶

设置 i、j、k：i、j 分别扫描 A、B，较小元素写入 C；某一表耗尽后，把另一表剩余部分整体接到 C 后。

合并前检查 C 的容量是否至少为 A.length+B.length。
时间复杂度 \(O(m+n)\)，结果表所需空间为 \(O(m+n)\)；除结果表外只用常数变量。
相等时先取哪一边要与题目对稳定性的要求一致。

💡 这是后续归并排序、链表交并集的基础模板。

回源 · PDF 第 36 页 · b_36_14；PDF 第 36 页 · b_36_15；PDF 第 37 页 · b_37_0；PDF 第 37 页 · b_37_1；PDF 第 37 页 · b_37_3

块交换和循环左移为什么都能用“三次逆置”？（2.2 综合应用题 07；2010 统考真题）¶

把原序列写成两段 ab，目标是 ba。恒等式为

\[ (a^Rb^R)^R=ba. \]

Q07 可先整体逆置，再分别逆置新序列的前后两段。
2010 左移 \(p\) 位可依次逆置 [0,p-1]、[p,n-1]、[0,n-1]。
两种写法本质相同，只是三次逆置的顺序不同。
时间 \(O(n)\)、空间 \(O(1)\)；辅助数组法虽也是 \(O(n)\) 时间，但需 \(O(p)\) 空间。

💡 先抽象成 ab→ba，再写逆置区间，不要靠背下标。

回源 · PDF 第 37 页 · b_37_4；PDF 第 37 页 · b_37_5；PDF 第 37 页 · b_37_7；PDF 第 38 页 · b_38_8；PDF 第 38 页 · b_38_10；PDF 第 38 页 · b_38_11；PDF 第 39 页 · b_39_1；PDF 第 39 页 · b_39_2

递增顺序表中“找到就与后继交换，找不到就插入”怎样一次定位？（2.2 综合应用题 08）¶

先用折半查找定位：

若找到 x 且它不是表尾，与后继交换；若它已是最后一个元素，则无后继可换。
若查找失败，循环结束时 low>high，插入位置是 high+1（也即 low）；从表尾向后搬移，腾出位置再插入。

查找为 \(O(\log n)\)，但失败后的插入可能搬移 \(O(n)\) 个元素，所以整个操作最坏仍为 \(O(n)\)；空间 \(O(1)\)。

回源 · PDF 第 37 页 · b_37_8；PDF 第 37 页 · b_37_9；PDF 第 37 页 · b_37_11；PDF 第 38 页 · b_38_0；PDF 第 38 页 · b_38_1

三个递增数组怎样在线性时间输出共同元素？（2.2 综合应用题 09）¶

用三个下标同时扫描：

三值相等：输出，并让三个下标都后移。
不相等：求当前最大值，只把小于最大值的那些下标后移。
任一数组扫描完即停止。

每个下标最多移动 \(n\) 次，时间 \(O(n)\)（一般长度时为 \(O(n_1+n_2+n_3)\)），空间 \(O(1)\)。

⚠️ 只移动一个最小值也可前进，但“所有小于当前最大值者一起移动”更直接。

回源 · PDF 第 38 页 · b_38_2；PDF 第 38 页 · b_38_3；PDF 第 38 页 · b_38_4；PDF 第 38 页 · b_38_7

两个等长升序序列的中位数怎样做到 O(logn) 和 O(1)？（2011 统考真题）¶

反复比较两序列当前中位数 \(a、b\)：

\(a=b\)：直接返回。
\(a<b\)：等量舍弃 A 的较小一半与 B 的较大一半。
\(a>b\)：对称处理。
每次都必须等量舍弃；奇偶长度下是否保留中点要按教材代码处理。

每轮把有效区间约减半，时间 \(O(\log n)\)、空间 \(O(1)\)。若线性同步访问到第 \(n\) 个元素，也可用 \(O(n)\) 时间、\(O(1)\) 空间得到答案。

回源 · PDF 第 39 页 · b_39_3；PDF 第 39 页 · b_39_5；PDF 第 39 页 · b_39_6；PDF 第 39 页 · b_39_7；PDF 第 40 页 · b_40_0；PDF 第 40 页 · b_40_1；PDF 第 40 页 · b_40_2

如何用“候选抵消 + 二次验证”找主元素？（2013 统考真题）¶

第一遍维护候选 c 与计数 count：相同则加 1，不同则减 1；计数归零后，用下一个元素重置候选。不同元素成对抵消后，若主元素存在，它一定是最后候选。

第二遍必须重新统计候选出现次数，只有严格大于 \(n/2\) 才返回，否则返回 -1。

时间 \(O(n)\)，空间 \(O(1)\)。
⚠️ 第一遍只能得到“可能的主元素”，不能省略验证。
教材应试提醒：先排序再统计虽非最优，正确也能获得较多步骤分；考场先保证完整答案。

回源 · PDF 第 40 页 · b_40_3；PDF 第 40 页 · b_40_4；PDF 第 40 页 · b_40_6；PDF 第 40 页 · b_40_7；PDF 第 40 页 · b_40_10；PDF 第 40 页 · b_40_12

怎样找数组中未出现的最小正整数？（2018 统考真题）¶

长度为 \(n\) 的数组，答案必在 \(1\sim n+1\)。

建立长度 \(n\) 的标记数组 B，B[x-1] 表示正整数 \(x\) 是否出现。
只标记 \(1\le A[i]\le n\)；非正数和大于 \(n\) 的值无需处理。
找到 B 中第一个 0，返回其下标加 1；若全为 1，返回 \(n+1\)。

时间 \(O(n)\)，空间 \(O(n)\)。这是教材给出的空间换时间方案。

回源 · PDF 第 40 页 · b_40_13；PDF 第 41 页 · b_41_0；PDF 第 41 页 · b_41_1；PDF 第 41 页 · b_41_2；PDF 第 41 页 · b_41_4

三个有序集合的最小三元组距离，为什么每次移动当前最小值？（2020 统考真题）¶

对三个当前值排序后，不妨设 \(a\le b\le c\)，则

\[ |a-b|+|b-c|+|c-a|=2(c-a). \]

距离只由当前最大值与最小值之差决定。

计算当前三元组距离并更新 Dmin。
只移动三个当前值中的最小值，才可能缩小区间；移动中间值或最大值不能让当前跨度变小。
任一数组到尾即停止；Dmin==0 可提前结束。

时间 \(O(|S_1|+|S_2|+|S_3|)\)，空间 \(O(1)\)。

回源 · PDF 第 41 页 · b_41_5；PDF 第 41 页 · b_41_6；PDF 第 41 页 · b_41_10；PDF 第 41 页 · b_41_11；PDF 第 41 页 · b_41_16；PDF 第 42 页 · b_42_0；PDF 第 42 页 · b_42_2

对每个 A[i] 求它与后缀元素乘积的最大值，为什么只需维护后缀最大最小值？（2025 统考真题）¶

从右向左扫描，维护后缀 [i,n-1] 的 Max 与 Min：

若 A[i]>=0，乘以后缀最大值 Max 才最大。
若 A[i]<0，乘以后缀最小值 Min（最负）才最大。
更新 Max、Min 后写入 res[i]。

一趟完成，时间 \(O(n)\)；除题目要求的输出数组 res 外，额外空间 \(O(1)\)。

⚠️ 负数会使大小关系反转，不能只维护后缀最大值。

回源 · PDF 第 42 页 · b_42_3；PDF 第 42 页 · b_42_4；PDF 第 42 页 · b_42_5；PDF 第 42 页 · b_42_7；PDF 第 42 页 · b_42_8

顺序存储的有序表中，哪一种给定操作平均能做到 O(1)？（2023 统考真题）¶

只有按序号获取第 \(i\) 个元素可由首地址和下标直接定位，平均 \(O(1)\)。

按值查找即使用折半也为 \(O(\log n)\)。
插入指定值要先定位并搬移元素，平均 \(O(n)\)。
删除第 \(i\) 个元素也要前移后续元素，平均 \(O(n)\)。

💡 易错点：有序能加速按值查找，却不能消除顺序表插入、删除的搬移成本。

回源 · PDF 第 34 页 · b_34_15；PDF 第 34 页 · b_34_16

双链表插入、删除时，怎样安排四个指针而不断链？（2016 Q32、2023 Q35 统考真题）¶

先画出“前驱—目标—后继”三结点，再按先保存旧链，再补双向关系检查语句。

删除 p：让 p->prev->next 跨过 p 指向后继，再令 p->next->prev 指向前驱。
在 p 后插入 s：先令 s->next=p->next；还要令旧后继的 prev 指向 s、s 的 prev 指向 p、p 的 next 指向 s。
题目已先执行部分语句时，要在执行后的图上继续推，而不是重新背完整模板。

这里的四指针模板默认 p 两侧都存在结点（如内部结点，或首尾哨兵已经补齐边界）。普通非循环双链表若在表头、表尾操作，必须判断相应前驱/后继是否为空，并分别更新头、尾指针，不能直接解引用空的 prev/next。

⚠️ 自指通常暴露顺序错误，如把后继的 prev 错指向其自身。

回源 · PDF 第 60 页 · b_60_14；PDF 第 60 页 · b_60_15；PDF 第 61 页 · b_61_5；PDF 第 61 页 · b_61_6；PDF 第 61 页 · b_61_8

给出结点地址和 next 地址时，怎样还原单链表并判断插入后的地址？（2016 Q33 统考真题）¶

把每个结点写成“本结点地址 → next 中保存的地址”，从表头元素开始沿地址追踪，先还原逻辑次序，再做插入。

本题插入后应满足 a→f→e→b 的局部关系，因此 a、f、e 的链接地址分别等于 f、e、b 的内存地址。教材据此得到 1014H、1010H、1004H。

⚠️ “结点本身的地址”与“结点 next 域中存的地址”是两列不同信息；不要按表格的物理行序当作链表顺序。

回源 · PDF 第 60 页 · b_60_16；PDF 第 60 页 · b_60_17；PDF 第 60 页 · b_60_18；PDF 第 60 页 · b_60_19

单链表语句序列题怎样逐句模拟，避免把 p、q 的角色看反？（2021 Q34、2024 Q36 统考真题）¶

每执行一句就更新一张小图，并始终标清“谁是待删/待移结点”。

2021 删除循环单链表首元：q=h->next 保存待删结点，h->next=q->next 断开；若 q 同时是尾结点，还要令尾指针 p 回到头结点 h，最后释放 q。
2024 移动后继结点：先令 q 指向 p->next，把 q 从原处摘下，再把 q 插到 h->next 之前；结果是q 所指结点移到头结点之后。

💡 固定四步：保存 → 摘下 → 接入 → 处理边界/释放。

回源 · PDF 第 60 页 · b_60_20；PDF 第 61 页 · b_61_0；PDF 第 61 页 · b_61_10；PDF 第 61 页 · b_61_11；PDF 第 61 页 · b_61_12

无序单链表中删除所有满足条件的结点，怎样统一处理？（2.3 综合应用题 01、04）¶

用 pre 指向当前结点 p 的前驱：

若 p 满足删除条件，先保存其后继，让 pre->next 跨过 p，再释放 p；此时 pre 不动。
若不删除，pre、p 同步后移。
Q01 条件是 p->data==x；Q04 换成严格开区间条件 min < p->data && p->data < max，即两个端点本身不删除。

教材还给出尾插重建法：保留结点重新接到表尾，删除结点释放，结束时务必把新尾的 next 置空。

时间 \(O(n)\)，空间 \(O(1)\)。

回源 · PDF 第 61 页 · b_61_14；PDF 第 62 页 · b_62_0；PDF 第 62 页 · b_62_3；PDF 第 62 页 · b_62_4；PDF 第 62 页 · b_62_7；PDF 第 64 页 · b_64_3；PDF 第 64 页 · b_64_4

怎样删除单链表中唯一的最小值结点？（2.3 综合应用题 02）¶

扫描时同时维护两对指针：p/pre 负责遍历，minp/minpre 记录当前最小结点及其前驱。扫描结束后用 minpre->next=minp->next 删除并释放最小结点。

时间 \(O(n)\)，空间 \(O(1)\)。
只记住最小结点而不记其前驱，最后仍需再次扫描才能删除。
不带头结点时要单独处理“最小值恰为首元”的情况。

回源 · PDF 第 62 页 · b_62_8；PDF 第 62 页 · b_62_9；PDF 第 63 页 · b_63_1；PDF 第 63 页 · b_63_2

单链表原地逆置有哪两种标准写法？（2.3 综合应用题 03）¶

两种都为 \(O(n)\) 时间、\(O(1)\) 空间：

头插重建：先令头结点的 next=NULL，逐个摘下原结点并插到头结点后。
三指针反转：pre、p、r 分别指向前驱、当前、后继；先用 r 保存旧后继，再令 p->next=pre，最后整体前进。

⚠️ 三指针法有两个边界：原首元逆置后成为尾结点，其 next 必须置空；全部完成后头结点要指向原尾结点。

回源 · PDF 第 63 页 · b_63_3；PDF 第 63 页 · b_63_4；PDF 第 63 页 · b_63_7；PDF 第 63 页 · b_63_9；PDF 第 64 页 · b_64_1；PDF 第 64 页 · b_64_2

两个单链表的公共结点为什么一定形成 Y 形，怎样在线性时间找到第一个公共结点？（2.3 综合应用题 05）¶

单链表每个结点只有一个 next。一旦两链表共享某个结点，之后的后缀必然全部重合，不可能再次分叉，所以拓扑只能是 Y 形。

算法：先求两表长度与尾结点；尾结点不同则无公共结点。若相同，让长表先走长度差，再让两个指针同步后移，第一次地址相同的位置就是第一个公共结点。

时间 \(O(len_1+len_2)\)，空间 \(O(1)\)。
⚠️ 比较的是结点地址，不是 data 值。

回源 · PDF 第 64 页 · b_64_7；PDF 第 64 页 · b_64_8；PDF 第 64 页 · b_64_10；PDF 第 64 页 · b_64_11；PDF 第 65 页 · b_65_0

怎样把 a1,b1,a2,b2,… 原地拆成 A 正序、B 逆序？（2.3 综合应用题 06）¶

遍历原链表时交替处理：奇数号结点用尾插法接到 A，保持 \(a_1,a_2,\dots\) 的顺序；偶数号结点用头插法接到 B，自然得到 \(\dots,b_2,b_1\)。

时间 \(O(n)\)，除 B 的头结点外只用常数指针。
头插会立即改写当前结点的 next，必须先用临时指针保存其原后继，否则断链。
A 的新尾最终要置 next=NULL。

回源 · PDF 第 65 页 · b_65_1；PDF 第 65 页 · b_65_2；PDF 第 65 页 · b_65_3；PDF 第 65 页 · b_65_4

递增单链表怎样原地去重？（2.3 综合应用题 07）¶

有序保证重复结点相邻。令 p 扫描：若 p->data==p->next->data，删除并释放后继 q，p 不动，继续检查新的后继；否则 p 后移。

时间 \(O(n)\)，空间 \(O(1)\)。
同一个值可能连续出现三次以上，所以删除一次后不能立即移动 p。

💡 和有序顺序表去重一样，都利用“相同值连续”；差别只是顺序表覆盖，链表断链并 free。

回源 · PDF 第 65 页 · b_65_5；PDF 第 65 页 · b_65_6；PDF 第 65 页 · b_65_8；PDF 第 65 页 · b_65_9；PDF 第 65 页 · b_65_10

两个递增链表求交集，“新建 C”与“复用 A”有什么本质差别？（2.3 综合应用题 08、09）¶

两题都用归并式双指针：小者后移，相等时保留一个公共值。

Q08 不破坏 A、B：相等时复制新结点，用尾插法接到 C；需要为结果结点分配空间。
Q09 交集存回 A：相等时复用 A 的结点，释放 B 的对应结点；不在交集中的结点全部释放，最后释放 B 的头结点。
时间均为 \(O(m+n)\)；若公共元素有 k 个，Q08 的结果结点占 \(O(k)\) 空间，Q09 的额外空间为 \(O(1)\)。

⚠️ 先看题目是否允许破坏原表，再决定“复制结点”还是“复用并释放”。

回源 · PDF 第 65 页 · b_65_11；PDF 第 66 页 · b_66_0；PDF 第 66 页 · b_66_2；PDF 第 66 页 · b_66_3；PDF 第 66 页 · b_66_4；PDF 第 67 页 · b_67_0；PDF 第 67 页 · b_67_1

怎样判断链表 B 是否为链表 A 的连续子序列？（2.3 综合应用题 10）¶

朴素匹配需记住本趟在 A 中的起点 pre：

相等时 A、B 指针同步后移。
失配时令起点移到 pre->next，A 从新起点重来，B 回到首结点。
B 先到尾则成功；A 到尾而 B 未完则失败。

这就是串的朴素模式匹配在链式存储上的对应形式。教材明确提示可结合后续字符串模式匹配思考优化；本节先掌握回退逻辑。

朴素写法最坏会从 A 的多个起点重新比较 B，时间复杂度为 \(O(mn)\)，额外空间 \(O(1)\)；后续学习模式匹配后再理解如何减少重复比较。

回源 · PDF 第 67 页 · b_67_2；PDF 第 67 页 · b_67_3；PDF 第 67 页 · b_67_5；PDF 第 67 页 · b_67_6；PDF 第 67 页 · b_67_7

怎样判断带头结点的循环双链表是否对称？（2.3 综合应用题 11）¶

令 p 从首元向右，q 从尾元向左，逐对比较。

值不同立即返回 0。
奇数个结点在 p==q 时结束；偶数个结点要在两指针交叉后结束，可用 q->next==p 判断。这样中间那一对仍会被比较。
时间 \(O(n)\)，空间 \(O(1)\)。

⚠️ 原书代码边界修正：原书写 p->next!=q 会在偶数长度时提前停在中间一对之前；两个数据结点时甚至一次都不比较。稳妥循环条件是 while (p!=q && q->next!=p)，每轮先比较当前两端，再分别后移/前移。

回源 · PDF 第 67 页 · b_67_8；PDF 第 67 页 · b_67_9；PDF 第 68 页 · b_68_0；PDF 第 68 页 · b_68_1；PDF 第 68 页 · b_68_2

两个循环单链表怎样连接后仍保持循环？（2.3 综合应用题 12）¶

先分别找到 h1、h2 的尾结点 p、q，再令 p->next=h2、q->next=h1，使第二个环接到第一个环后并闭合。

只有头指针时，找尾需要遍历，时间为 \(O(m+n)\)。
若题目直接给两个尾指针，则连接本身只改常数个指针，可为 \(O(1)\)。

⚠️ 带头结点时要确认题目希望保留几个头结点；本题教材代码把 h2 的头结点也接入新环。

回源 · PDF 第 68 页 · b_68_3；PDF 第 68 页 · b_68_4；PDF 第 68 页 · b_68_6

按访问频度递减排列的双链表，Locate 后怎样把结点移到正确位置？（2.3 综合应用题 13）¶

先顺序查找值为 x 的结点 p，并令 p->freq++。若 p 是首元，或其频度仍严格低于前驱（pre->freq > p->freq），位置不变；若与前驱同频也必须前移，否则不能满足“最近访问者排同频最前”。需要移动时：

把 p 从原位置摘下，补好前后双向链接。
沿 pre 向前找，越过所有频度小于或等于 p 的结点。
把 p 插到第一个频度大于它的结点之后。

这样既保持频度递减，也让最近访问者排在同频度结点之前。查找与移动最坏均为 \(O(n)\)，额外空间 \(O(1)\)。

回源 · PDF 第 68 页 · b_68_7；PDF 第 68 页 · b_68_8；PDF 第 68 页 · b_68_10；PDF 第 69 页 · b_69_0

不带头结点的单链表怎样原地循环右移 k 位？（2.3 综合应用题 14）¶

先遍历求表长 n 并找到尾结点，把尾结点接回原首元形成环；新尾是原表第 \(n-k\) 个结点，新首是它的后继。令 L 指向新首，再把新尾的 next 置空断环。

时间 \(O(n)\)，空间 \(O(1)\)。
题设有 \(0<k<n\)；若推广到任意 k，应先取 k%=n。

💡 链表旋转的稳定套路：先成环，再找新尾，最后断环。

回源 · PDF 第 69 页 · b_69_1；PDF 第 69 页 · b_69_2；PDF 第 69 页 · b_69_3；PDF 第 69 页 · b_69_5；PDF 第 69 页 · b_69_6

Floyd 快慢指针怎样判断有环，并进一步找到环入口？（2.3 综合应用题 15）¶

fast 每次走两步、slow 每次走一步；若无环，fast 会先到空；若有环，两者必在环内相遇。

找到入口：相遇后令一个指针回到 head，另一个留在相遇点，二者都改为每次一步；下一次相遇处就是环入口。教材用 \(a=nr-x\) 说明两段路程相等。

时间 \(O(n)\)，空间 \(O(1)\)。
⚠️ 每次让 fast 走两步前，都要检查 fast 与 fast->next 非空。

回源 · PDF 第 69 页 · b_69_7；PDF 第 69 页 · b_69_9；PDF 第 69 页 · b_69_10；PDF 第 70 页 · b_70_0；PDF 第 70 页 · b_70_2；PDF 第 70 页 · b_70_3

偶数长度单链表的最大孪生和怎样做到 O(n) 时间、O(1) 空间？（2.3 综合应用题 16）¶

三步：

快慢指针找中点：按本题偶数长度的原书写法，slow 从首元、fast 从第二个结点出发，二者分别每次走 1、2 步，使 slow 停在前半段末尾。
原地逆置后半段。
用两个指针分别从前半段首元与逆置后的后半段首元同步扫描，更新最大和。

时间 \(O(n)\)、额外空间 \(O(1)\)。

💡 “首尾配对”在单链表上难以从尾向前走，所以先把后半段逆置，把问题变成两个正向链表的同步扫描。

回源 · PDF 第 70 页 · b_70_4；PDF 第 70 页 · b_70_5；PDF 第 70 页 · b_70_6；PDF 第 70 页 · b_70_7；PDF 第 71 页 · b_71_1

一趟扫描怎样找到单链表倒数第 k 个结点？（2009 统考真题）¶

让 p、q 初始都指向首元：先让 p 走满 k 步（这时 p 可以恰好成为 NULL），再让二者同步后移；以 p 到达 NULL 为终点，此时 q 正好指向倒数第 k 个结点。若 p 尚未走满 k 步就已为空，则 \(k\) 大于表长，查找失败。

教材实现用 count 控制 q 何时开始移动，并在结束时检查 count==k，处理 \(k\) 大于表长的失败情况。

时间 \(O(n)\)，空间 \(O(1)\)，只扫描一遍。
⚠️ 评分说明明确：一遍扫描可得满分；多遍扫描、递归或与 k 同阶辅助数组即便正确也会失分。

回源 · PDF 第 71 页 · b_71_2；PDF 第 71 页 · b_71_3；PDF 第 71 页 · b_71_4；PDF 第 71 页 · b_71_10；PDF 第 71 页 · b_71_13；PDF 第 71 页 · b_71_15

两个单词链表的共同后缀起点怎样找到？（2012 统考真题）¶

共同后缀就是两个链表的第一个公共结点。先求长度 \(m、n\)，让较长链表先走 \(|m-n|\) 步，使两个指针到表尾的剩余距离相同；再同步后移，第一次指向同一地址的位置就是共同后缀起点。

时间 \(O(len_1+len_2)\)（也可写 \(O(\max(len_1,len_2))\) 的同阶扫描口径），空间 \(O(1)\)。
⚠️ 不能比较字符值；相同字符未必是共享的同一结点，必须比较指针地址。

回源 · PDF 第 71 页 · b_71_16；PDF 第 71 页 · b_71_17；PDF 第 72 页 · b_72_0；PDF 第 72 页 · b_72_1；PDF 第 72 页 · b_72_2；PDF 第 72 页 · b_72_5

怎样删除单链表中绝对值重复的结点？（2015 统考真题）¶

题设给出 \(|data|\le n\)，因此可用长度 \(n+1\) 的标记数组 q：扫描结点时令 m=abs(data)；若 q[m]==0，标记并保留；否则断链、释放该结点。

只保留第一次出现者。
时间 \(O(m)\)（m 为链表结点数），空间 \(O(n)\)。
⚠️ 数值可能为负，标记下标必须取绝对值；删除后前驱不移动。

💡 题设中的值域上界不是闲信息，它在提示“用空间换一趟扫描”。

回源 · PDF 第 72 页 · b_72_6；PDF 第 72 页 · b_72_7；PDF 第 72 页 · b_72_8；PDF 第 73 页 · b_73_1；PDF 第 73 页 · b_73_2；PDF 第 73 页 · b_73_3

怎样把链表重排为 a1,an,a2,a(n-1),…？（2019 统考真题）¶

目标是前半段顺序与后半段逆序交替出现：

快慢指针找中点并断开前后两段。边界要由初始化或循环条件固定：例如原书令慢指针从头结点、快指针从头结点出发，快指针每轮尝试走两步，使慢指针最终落在应保留的前半段末尾；不要笼统地让两个指针都从首元出发而忽略奇偶长度。
原地逆置后半段；题目要求 \(O(1)\) 空间，不能用栈。
从两段各取一个结点，交替穿插。

三步均为 \(O(n)\)，总时间 \(O(n)\)、额外空间 \(O(1)\)。

⚠️ 若不先逆置后半段，每次取原链尾都要重新遍历，会退化为 \(O(n^2)\)。

回源 · PDF 第 73 页 · b_73_4；PDF 第 73 页 · b_73_5；PDF 第 73 页 · b_73_6；PDF 第 73 页 · b_73_8；PDF 第 74 页 · b_74_0；PDF 第 74 页 · b_74_1

【原书归纳总结与思维拓展】第2章¶

统考算法题的“三段式”答案怎样写，才能先稳拿过程分？¶

按教材固定结构作答：

基本设计思想：说清数据如何移动、指针怎样推进、循环何时停止。
C/C++ 代码或伪代码：关键操作写注释，复杂边界可用文字补足。
时空复杂度：分别说明每一阶段，再取总阶。

教材明确提醒：正确的数据结构定义和清晰思想通常已能获得相当部分分数；考场先把完整路线写出来，再补代码细节，不要因追求最优解而交白卷。

回源 · PDF 第 74 页 · b_74_2；PDF 第 74 页 · b_74_3；PDF 第 74 页 · b_74_4；PDF 第 74 页 · b_74_5；PDF 第 74 页 · b_74_8

顺序表删除题怎样在“稳定压缩”和“表尾补洞”之间选择？¶

要求保序：用读写双下标或“删除计数 k”，每个保留元素最多移动一次，\(O(n)\)、\(O(1)\)。
不要求保序且只删少量位置：可用表尾元素补洞，省去整体搬移。
反复调用单元素删除会让每次都搬移后缀，最坏退化到 \(O(n^2)\)。

判断关键词：看到“保持原有次序、稳定”选压缩；看到“空位由最后元素填补”就直接补洞。

回源 · PDF 第 35 页 · b_35_11；PDF 第 35 页 · b_35_14；PDF 第 36 页 · b_36_0；PDF 第 36 页 · b_36_5；PDF 第 36 页 · b_36_6

线性表算法题最常复用的五类方法分别解决什么问题？¶

头插法：逆置、使抽取序列反向。
尾插法：保持原顺序、构造新结果表。
逆置法：数组块交换、链表后半段反向。
归并法：两个有序表的合并、交集。
双指针法：找中点、倒数第 k 个、公共后缀、判环、两端配对。

顺序表还常结合随机访问、折半查找和排序；链表则优先思考如何保存前驱与后继、怎样避免断链。

回源 · PDF 第 74 页 · b_74_6

修改链表指针时，怎样用“先保存、再断开、后接入”避免断链？¶

统一检查顺序：

用临时指针保存稍后仍要访问的旧后继。
把目标结点从原链摘下，并补好原位置的链接。
把结点接入新位置；双链表要同时补 next 与 prev。
最后处理头尾、空表、单结点和 free。

⚠️ 不要机械背语句序号。题目若已执行两句，必须在当前图上继续；出现某结点的指针指回自身，通常说明赋值顺序或对象写错。

回源 · PDF 第 58 页 · b_58_11；PDF 第 58 页 · b_58_12；PDF 第 59 页 · b_59_8；PDF 第 59 页 · b_59_9；PDF 第 59 页 · b_59_10

数组两数之和怎样在 O(nlogn) 内找出且每个元素只输出一次？（思维拓展）¶

先用 \(O(n\log n)\) 的算法排序，再令 i 指向最小端、j 指向最大端：

A[i]+A[j]<x：i 右移。
A[i]+A[j]>x：j 左移。
等于 x：输出这一对，然后 i、j 同时向中间移动；若题目要求按值去重，还应跨过相同值。

排序 \(O(n\log n)\)，双指针扫描 \(O(n)\)，总时间 \(O(n\log n)\)；原地排序时额外空间取决于所选排序算法。

回源 · PDF 第 74 页 · b_74_9；PDF 第 74 页 · b_74_10；PDF 第 74 页 · b_74_11；PDF 第 74 页 · b_74_12

【易混点】第2章成对概念对照¶

概念 A	概念 B	一句话切分
线性表	顺序表 / 链表	逻辑结构 vs 两种存储结构
静态分配	动态分配	编译时定死、占满溢出 vs 运行时可扩容；⚠️ 两者都是顺序存储
头指针	头结点	永远指向第一个结点，任何链表都有 vs 只有带头结点的链表才有，数据域不放有效数据
位序	数组下标	从 1 开始 vs 从 0 开始
插入平均移动 n/2	删除平均移动 (n−1)/2	顺序表两个必背结论
头插法	尾插法	逆序、无须尾指针 vs 正序、需维护尾指针 r
单链表插入①②	双链表插入①~④	s->next 先接 vs ①必须在④之前
循环单链表判空	单链表判空	L->next == L vs L == NULL 或 L->next == NULL
循环单链表用尾指针	用头指针	首尾插入都 O(1) vs 表尾插入 O(n)
静态链表 next = −1	单链表 next = NULL	结束标志不同
存储密度	—	顺序表高（只存数据） vs 链表 < 1（多存指针）

【必背数字】第2章¶

数字	含义
1 ≤ i ≤ length+1 / 1 ≤ i ≤ length	顺序表插入 / 删除的合法位置范围
n/2 · (n−1)/2	顺序表插入 / 删除的平均移动次数
O(1) / O(n)	顺序表按序号查找 / 链表按序号查找
O(log₂n)	有序顺序表折半查找
O(1)	已知结点指针时的后插；双链表已知结点的增删；循环单链表用尾指针的首尾插入
第 0 个结点	遍历时头结点的约定位序（j 从 0 开始）
next == −1	静态链表的结束标志
L->next == L	循环单链表判空
L->prior == L 且 L->next == L	循环双链表判空

【口诀速记】第2章¶

维度	口诀	解释
顺序表两个平均	插 n/2，删 (n−1)/2	插入/删除的平均移动次数，插入比删除多挪半个
头指针 vs 头结点	头指针人人有，头结点看情况	头指针永远指向第一个结点；头结点只有带头结点的链表才有
双链表插入	先接新结点两端，再断旧连接	① s->next=p->next 必须在 ④ p->next=s 之前
循环链表判空	单链指自己，双链前后都指自己	循环单链表 L->next==L；循环双链表 L->prior==L 且 L->next==L
循环单链表	尾指针一手抓两头	只设尾指针 r，表头表尾插入都是 O(1)
静态链表	结束标志是 −1，不是 NULL	next 存的是数组下标（游标），不是真指针
选型	规模稳定看下标选顺序，动态增删选链式	顺序表随机存取 O(1)，链表增删只改指针

回源 · PDF 第 25 页 · b_25_3；PDF 第 25 页 · b_25_4

【解题路线】第2章：线性表算法题怎么下手¶

① 先判存储结构 —— ⚠️ 顺序表能随机存取（可用下标运算、折半查找）；链表只能顺序走
② 顺序表的三个套路：双指针原地覆盖（删除/去重，一个读一个写）、首尾交换实现逆置、有序表用折半定位
③ 链表的四个套路：
⚠️ 带头结点 —— 省去对首元素的特判
快慢指针 —— 找中点、找倒数第 k 个、判环
⚠️ 头插法 —— 天然实现逆置
归并两个有序链表 —— 只改指针不申请新结点
④ 动指针前一定先画图，确认哪两步顺序不能颠倒（s->next = p->next 必须在 p->next = s 之前）

⚠️ 两个 O(1) 技巧的边界：删除给定结点用"复制后继再删后继"，但尾结点不适用；前插用"后插 + 换数据"，要求数据可复制。

回源 · PDF 第 25 页 · b_25_5；PDF 第 25 页 · b_25_6

第2章 线性表