数据结构第 2 章：线性表

408 数据结构「线性表」复习：核心知识点、真题题型、通用解法与易错点。

本章依据本站 408 真题「第 2 章线性表」和对应的 408 模拟选择题「第 2 章线性表」 整理。站内真题把本章分成“顺序存储”和“链式存储”，真题尤其集中在数组原地算法、双指针、单链表综合操作、双链表指针修改；模拟题又补充了静态链表和不同存储结构的复杂度判断。(Any Docs)

这章非常重要，因为它实际上是整个数据结构“算法题基本功”的起点。后面的树、图、查找、排序都会反复用到这里形成的几种思维：

数组：下标、原地交换、双指针、空间换时间。 链表：找位置、断链、保存后继、重新连接。

一、本章到底要学什么？

先建立完整地图。

知识块	408重要性	主要题型
线性表基本概念	★★	定义、逻辑关系
顺序表特点	★★★	插入删除复杂度、随机访问
顺序表算法	★★★★★	原地逆置、双指针、特殊数组算法
单链表基本操作	★★★★★	插入、删除、遍历
单链表综合算法	★★★★★	快慢指针、逆置、拆分、合并
双链表	★★★★	插入删除语句判断
循环链表	★★★	首尾特殊情况
静态链表	★★	数组下标模拟指针
顺序表与链表比较	★★★★	时间复杂度判断

一个关键结论是：

真正需要重点练的不是“顺序表插入代码怎么写”，而是怎么根据题目条件设计一个尽可能快的算法。

站内的 2010、2011、2013、2018、2019、2020 真题尤其能体现这一点。(Any Docs)

二、线性表的基本概念

线性表可以写成

L = (a_{1}, a_{2}, \dots, a_{n})

其特点是：

除第一个元素外，每个元素有唯一直接前驱；除最后一个元素外，每个元素有唯一直接后继。

注意：

“线性”说的是逻辑关系，不是物理存储方式。

例如：

顺序表逻辑上是

a_{1} \to a_{2} \to a_{3}

物理上通常也连续。

而链表逻辑上仍然是

a_{1} \to a_{2} \to a_{3}

但三个结点在内存中完全可以位于三个毫不相关的位置。

所以考试看到“地址乱七八糟”，千万不要按地址大小判断元素顺序，必须沿 next 找。

这正是 2016 年真题考查的内容。

三、顺序表和链表的根本差别

这是后面几乎所有复杂度题的基础。

操作	顺序表	单链表
按序号访问第 $i$ 个元素	$O (1)$	$O (n)$
按值查找	$O (n)$	$O (n)$
已知位置插入	通常 $O (n)$	已知前驱后 $O (1)$
已知结点删除	需移动元素 $O (n)$	若知道前驱可 $O (1)$
存储密度	高	较低
扩容	可能需要重新分配	动态申请即可
随机访问	支持	不支持

最核心的一句话：

顺序表擅长“访问”，链表擅长“修改链接”。

但一定注意：

“链表插入删除是 $O (1)$ ”这句话有条件。

必须是已经找到插入或删除位置。

例如要删除单链表第 $k$ 个结点，首先找到第 $k - 1$ 个结点通常就需要

O (n)

所以整个操作仍然是

O (n)

四、题型一：数组原地变换——逆置法

真题：2010 年循环左移

题目核心：

有数组
$R = (X_{0}, X_{1}, \dots, X_{n - 1})$
要循环左移 $p$ 个位置，变成
$(X_{p}, \dots, X_{n - 1}, X_{0}, \dots, X_{p - 1})$
要求时间和空间尽可能高效。(Any Docs)

这是一道极其重要的“原地数组变换”模板题。

设

A = (X_{0}, \dots, X_{p - 1})

B = (X_{p}, \dots, X_{n - 1})

原序列就是

A B

目标是

B A

利用逆置：

(A^{R} B^{R})^{R} = B A

于是三步：

A^{R} B

再得到

A^{R} B^{R}

最后整体逆置：

(A^{R} B^{R})^{R} = B A

例如

[1, 2, 3, 4, 5, 6, 7]

左移 $3$ 位。

先逆置前 3 个：

[3, 2, 1, 4, 5, 6, 7]

再逆置后 4 个：

[3, 2, 1, 7, 6, 5, 4]

全部逆置：

[4, 5, 6, 7, 1, 2, 3]

复杂度：

T (n) = O (n)

S (n) = O (1)

站内也给出的正是“三次逆置”方案。(Any Docs)

这一题真正要学什么？

以后看到：

“循环移动”“前后两段互换”“数组原地调整”

第一反应就是：

能否拆成若干段，然后利用逆置？

例如右移 $p$ 位，可以直接变形为左移

n - p

位。

五、题型二：两个有序数组——不要傻傻合并

真题：2011 年两个等长升序序列的中位数

题目：

两个长度均为 $n$ 的升序数组 $A, B$ ，定义两个序列合并后的第 $n$ 小元素为中位数，要求尽可能高效地求出来。(Any Docs)

最容易想到：

两个数组归并。

复杂度：

O (n)

空间可以做到

O (1)

但这还不是最优。

因为题目给了一个极重要条件：

两个数组本身已经有序。

于是可以像二分查找一样不断排除一半。

取两个数组当前区间的中位数

m_{A}

和

m_{B}

若

m_{A} = m_{B}

直接得到答案。

如果

m_{A} < m_{B}

那么总体中位数不可能出现在：

$A$ 的过小部分，以及 $B$ 的过大部分。

于是同时舍弃两边等量元素。

候选规模约变为原来的

\frac{1}{2}

所以

T (n) = T (\frac{n}{2}) + O (1)

最终：

T (n) = O (lo g n)

空间：

O (1)

站内真题解析也采用了这种二分缩小候选范围的方法。(Any Docs)

这里有一个非常重要的考试意识

只要看到：

“有序”

就应该立刻想到：

二分、双指针、归并

而不是直接写双层循环。

六、题型三：主元素——“不同元素互相抵消”

真题：2013 年主元素

题目定义：

若某元素 $x$ 出现次数

m > \frac{n}{2}

则称 $x$ 为主元素。

例如

0, 5, 5, 3, 5, 7, 5, 5

主元素为 $5$ 。

要求尽可能高效地找到主元素。(Any Docs)

解法：Boyer-Moore 多数投票

关键性质：

若主元素出现超过一半，那么即使不断执行：

删除两个值不同的元素

最终主元素也不可能被完全消掉。

维护：

candidate：候选主元素

count：票数

扫描数组。

遇到相同元素：

co u n t + +

遇到不同元素：

co u n t - -

若

co u n t = 0

则重新选择候选。

例如：

[5, 1, 5, 2, 5, 5, 3]

过程可以理解为：

5 \leftrightarrow 1

抵消；

5 \leftrightarrow 2

抵消；

最终因为 $5$ 数量超过其他所有元素总和，所以 $5$ 一定留下。

但是为什么必须再扫描一次？

因为投票算法只能得到：

“如果主元素存在，那么这个 candidate 一定是它。”

不保证主元素一定存在。

因此还要重新统计：

c n t (c an d i d a t e)

如果

c n t (c an d i d a t e) > \frac{n}{2}

才真正返回它。

复杂度：

O (n)

空间：

O (1)

站内真题也特别强调了“第一趟筛选，第二趟验证”。(Any Docs)

七、题型四：利用元素范围建立“下标映射”

这是408算法题非常喜欢的一类思想。

真题：2018 年最小未出现正整数

题目：

给定长度为 $n$ 的整数数组，找其中没有出现的最小正整数。

例如：

[- 5, 3, 2, 3]

答案：

1

而

[1, 2, 3]

答案：

4

(Any Docs)

第一步：先缩小答案范围

这是这题最关键的一步。

长度只有 $n$ 。

如果

1, 2, \dots, n

全部出现，那么答案最多是

n + 1

否则答案就在

1, 2, \dots, n

中。

因此真正关心的只有：

[1, n]

其他数字，例如：

- 100, 0, 999999

全部可以忽略。

标准思维一：标记数组

建立数组 seen[n+1]。

若出现数字 $x$ ：

see n [x] = 1

最后找到第一个没有出现的。

复杂度：

O (n)

空间：

O (n)

这是考场上非常稳的一种做法。

更进一步：直接利用原数组

本站里的解析采用了更强的原地做法：

把

x

放到

A [x - 1]

的位置。

于是理想状态：

A [0] = 1

A [1] = 2

\dots

最后扫描：

若第一个

A [i] \neq = i + 1

那么答案就是

i + 1

如果全部满足，则答案：

n + 1

这样能够达到

O (n)

时间，

O (1)

额外空间。(Any Docs)

这一类型的统一思想

以后看到：

元素取值范围很小

例如：

0 \leq x \leq n

或者

∣ x ∣ \leq n

都应该立刻想到：

用值直接作为数组下标

后面的 2015 年链表删除重复绝对值，还是这个思想。

八、题型五：多个有序数组——多指针贪心

真题：2020 年三个集合最小距离

有三个升序数组

S_{1}, S_{2}, S_{3}

选择

a \in S_{1}, b \in S_{2}, c \in S_{3}

定义

D = ∣ a - b ∣ + ∣ b - c ∣ + ∣ c - a ∣

求最小值。(Any Docs)

例如题目给出的：

S_{1} = {- 1, 0, 9}

S_{2} = {- 25, - 10, 10, 11}

S_{3} = {2, 9, 17, 30, 41}

最优三元组：

(9, 10, 9)

第一关键：化简距离公式

设三者排序后：

x \leq y \leq z

那么

D = (y - x) + (z - y) + (z - x)

所以

D = 2 (z - x)

即

D = 2 (max - min)

因此问题完全变成：

如何让三个当前元素的最大值和最小值尽可能接近？

第二关键：为什么移动最小值？

假设当前：

a < b < c

距离取决于：

c - a

如果移动 $b$ 或 $c$ ：

它们只会继续增大，因为数组是升序。

这样不可能减小当前最小值 $a$ 与最大值之间的差距。

所以唯一可能改善答案的方法：

移动当前最小值的指针

于是三个指针只向前走。

总复杂度：

O (n_{1} + n_{2} + n_{3})

额外空间：

O (1)

这正是站内真题给出的算法。(Any Docs)

九、顺序表算法题总结：看见什么条件想到什么算法？

题目特征	第一反应
原地循环移动	分段逆置
有序数组	双指针 / 二分
出现次数超过一半	Boyer-Moore
元素范围有限	标记数组 / 原地哈希
多个有序集合	多指针扫描
要求 $O (1)$ 空间	交换、逆置、指针，而不是复制数组

到这里，顺序存储部分真正需要掌握的核心思维已经完整了。

十、链表第一大题型：看懂“地址”而不是看元素排列

2016 真题：根据物理地址插入结点

题目给出：

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

表头元素为 $c$ 。

所以从 $c$ 开始：

c (1008 H) \to a (1000 H) \to e (1010 H) \to b (1004 H) \to d (100 C H)

这才是真正的逻辑顺序。

现在结点 $f$ 放在地址 1014H，插到 $a, e$ 之间。(Any Docs)

局部原来：

a \to e

现在：

a \to f \to e

所以：

a . n e x t = 1014 H

f . n e x t = 1010 H

而

e . n e x t = 1004 H

不变。

答案：

1014 H, 1004 H, 1010 H

模拟题：删除 a

网站模拟题进一步要求在同一个结构里删除 $a$ 。

原来：

c \to a \to e

删除后：

c \to e

因此：

c . n e x t = 1010 H

而 $e$ 仍然指向 $b$ ：

e . n e x t = 1004 H

答案是

1010 H, 1004 H

。(Any Docs)

这两道题组合起来非常值得记。

核心不是背地址，而是：

先画逻辑链，再修改 next

十一、链表第二大题型：插入删除的语句顺序

这是本章选择题最高频陷阱之一。

核心原则：

永远不要先覆盖掉以后还要用的指针。

十二、单链表头插法

模拟题：

带头结点单链表，头指针为 $L$ 。希望插入顺序与链中顺序相反，应如何插入新结点 $p$ ？(Any Docs)

显然是头插法：

p->next = L->next;
L->next = p;

注意顺序绝对不能交换。

如果写：

L->next = p;
p->next = L->next;

第二句中的

L->next

已经变成 $p$ 。

结果：

p->next = p;

形成自环。

这是典型考试陷阱。

十三、双链表删除——四个指针看起来复杂，其实只有两条边

2016 真题

删除双向循环链表中 $p$ 指向的结点。(Any Docs)

删除前：

A \leftrightarrow p \leftrightarrow B

删除后：

A \leftrightarrow B

需要修改：

B . p r e v = A

以及：

A . n e x t = B

即：

p->next->prev = p->prev;
p->prev->next = p->next;
free(p);

答案 D。(Any Docs)

最好不要死背

画图：

A <----> p <----> B

删掉 $p$ ：

A <------------> B

再问：

谁的 next 变了？

A。

谁的 prev 变了？

B。

立刻得到答案。

十四、双链表插入——最容易考“修改次序”

2023 真题

要在 $p$ 之后插入 $s$ 。

题目已经执行：

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

问还需要什么？(Any Docs)

原来：

p \leftrightarrow q

目标：

p \leftrightarrow s \leftrightarrow q

执行前两句后：

s . n e x t = q

p . n e x t = s

但：

s . p r e v

还没正确设置，

而

q . p r e v

仍指向 $p$ 。

此时有：

s->next->prev

其实仍然是 $p$ 。

所以：

s->prev = s->next->prev;
s->next->prev = s;

答案 C。(Any Docs)

这里特别容易误选：

p->next->prev = s;

为什么错？

因为执行了：

p->next = s;

以后

p->next

就是 $s$ 。

所以

p->next->prev = s;

实际上成为：

s->prev = s;

形成自指。

十五、模拟题：在 p 前插入 x

站内模拟题把 2023 真题反过来：

双向循环链表，在 $p$ 前插入 $x$ 。(Any Docs)

设：

q = p . p r e v

目标：

q \leftrightarrow x \leftrightarrow p

正确顺序：

x->next = p;
x->prev = p->prev;
p->prev->next = x;
p->prev = x;

为什么最后才：

p->prev = x;

因为旧的

p->prev

还要帮助找到 $q$ 。

这就是链表语句排序题的统一法则：

先读取旧关系，再覆盖旧关系

十六、循环链表：重点不是“循环”，而是边界

2021 真题

带头结点非空单循环链表。

$h$ 为头指针，

$p$ 为尾指针。

删除第一个数据结点。(Any Docs)

设第一个结点为 $q$ ：

q = h->next;
h->next = q->next;

通常这样就够了。

但是题目还有一个特殊情况：

链表只有一个数据结点。

此时

q = p

删除后尾指针不能继续指向已经释放的 $q$ 。

因此必须：

if (p == q)
    p = h;

最后：

free(q);

所以答案 D。(Any Docs)

这种题最爱考什么？

不是主体算法。

而是：

n = 0

n = 1

首结点、

尾结点、

只有一个结点。

所以做链表选择题最后一定要问自己：

“如果链表只有一个元素，还成立吗？”

十七、链表代码执行结果题

2024 真题

给定非首非尾结点 $p$ ，执行：

q = p->next;
p->next = q->next;
q->next = h->next;
h->next = q;

问结果是什么。(Any Docs)

不要整体看。

逐段解释。

前两句：

q = p->next;
p->next = q->next;

原来：

p \to q \to r

变成：

p \to r

所以 $q$ 被摘下来。

后两句：

q->next = h->next;
h->next = q;

这是标准头插。

所以最终：

把 q 从原位置移动到了链表最前面

答案 D。(Any Docs)

十八、链表代码阅读的万能方法

不要在脑子里直接执行四五行指针语句。

应该每执行一条就画：

A -> B -> C -> D

例如：

q = p->next;

就在图上标记 $q$ 。

然后：

p->next = q->next;

把对应箭头擦掉重画。

408 指针题其实是“画箭头题”，不是 C 语言题。

十九、链表算法第一大模板：快慢指针

2009 真题：倒数第 k 个结点

题目：

带头结点的单链表，只给头指针 list，要求不改变链表，尽可能高效地查找倒数第 $k$ 个结点。(Any Docs)

普通方法

先遍历一次求长度：

n

再找到：

n - k + 1

位置。

需要两趟。

虽然仍然是

O (n)

但可以更漂亮。

快慢指针

设置：

f a s t, s l o w

都从首元结点出发。

让 fast 先走 $k$ 步。

这样二者保持距离：

k

然后一起移动。

当

f a s t = N U LL

时，

slow 正好是倒数第 $k$ 个结点。

例如链表：

1 \to 2 \to 3 \to 4 \to 5

找倒数第 2 个。

fast 先走 2 步。

之后同步前进，fast 到 NULL 时：

s l o w = 4

答案正确。

复杂度：

O (n)

空间：

O (1)

站内真题也是这一方案。(Any Docs)

二十、快慢指针还能解决哪些题？

这是必须扩展出去的。

找链表中点：

fast 每次走两步，

slow 每次走一步。

当 fast 到尾部时：

s l o w

就在中间。

判断环：

还是 fast 两步、slow 一步。

有环一定会相遇。

寻找倒数第 $k$ 个：

保持两个指针相差 $k$ 个位置。

所以快慢指针的本质不是固定套路，而是：

人为制造两个指针之间的位置关系

二十一、链表算法第二模板：尾部对齐

2012 真题：两个单词的公共后缀

题目用链表保存 "loading" 和 "being"。

如果两个单词有相同后缀，则相同后缀结点共享存储空间。

要求找到公共后缀的起点。(Any Docs)

例如：

loading ─┐
         i -> n -> g -> NULL
being ───┘

注意：

这里不是字符相同。

而是两个指针最终指向同一个物理结点。

为什么不能两个指针直接同时走？

因为链表长度可能不同。

例如：

A: x -> x -> x -> c -> d
B:           y -> c -> d

如果同时从表头开始，很可能永远无法同时到公共结点。

正确办法：尾部对齐

设长度分别：

m, n

长链表先走：

∣ m - n ∣

步。

之后两个指针到尾结点的距离相同。

然后同步走。

第一次满足：

p = q

即找到公共后缀起始结点。

复杂度：

O (m + n)

空间：

O (1)

。(Any Docs)

二十二、“倒数第 k 个”和“公共后缀”其实是一类题

表面上：

2009 年问倒数第 $k$ 个；

2012 年问公共结点。

但底层思想完全一样：

先制造一个距离差，再同步移动

2009：

人为制造距离

k

2012：

人为消除长度差

∣ m - n ∣

一旦理解这一层，两道题就不需要分别背。

二十三、链表算法第三模板：辅助数组换时间

2015 真题

单链表有 $m$ 个整数，且

∣ d a t a ∣ \leq n

要求对于绝对值相同的结点只保留第一次出现者，其余删除。(Any Docs)

例如：

21, - 15, - 15, - 7, 15

由于：

∣ - 15∣ = ∣15∣

后面重复的都应该删掉。

如果不用额外空间

每出现一个元素，都向前查是否出现过。

最坏：

O (m^{2})

利用题目条件

因为：

∣ d a t a ∣ \leq n

所以绝对值只能：

0, 1, 2, \dots, n

建立：

see n [0 \dots n]

遇到：

∣ p . d a t a ∣ = x

检查：

see n [x]

若没出现：

保留。

若出现：

删除。

复杂度：

O (m + n)

空间：

O (n)

。(Any Docs)

二十四、删除链表结点时为什么通常需要 pre？

设：

pre -> p -> q

要删除 $p$ 。

需要：

pre->next = p->next;
free(p);
p = pre->next;

因为单链表不能直接由 $p$ 找前驱。

所以扫描过程中通常同时维护：

pre
p

这是所有“边遍历边删除”问题的标准结构。

二十五、本章最综合真题：2019 年链表重排

这一题非常值得反复练。

题目

原链表：

L = (a_{1}, a_{2}, a_{3}, \dots, a_{n})

要求原地变成：

L = (a_{1}, a_{n}, a_{2}, a_{n - 1}, a_{3}, a_{n - 2}, \dots)

要求空间：

O (1)

时间尽可能高效。(Any Docs)

二十六、先分析目标，而不是直接写代码

假设：

1, 2, 3, 4, 5, 6

目标：

1, 6, 2, 5, 3, 4

观察发现：

从左边取一个，

再从右边取一个。

但单链表只能向后访问。

无法直接：

6, 5, 4

倒着访问。

怎么办？

把后半段逆置。

二十七、第一步：找链表中点

使用快慢指针：

slow 每次：

1

步，

fast 每次：

2

步。

对于：

1 \to 2 \to 3 \to 4 \to 5 \to 6

最后把链表拆成：

1 \to 2 \to 3

和

4 \to 5 \to 6

。

二十八、第二步：逆置后半段

把：

4 \to 5 \to 6

变成：

6 \to 5 \to 4

这是单链表必须掌握的核心代码：

prev = NULL;
cur = head;

while (cur != NULL) {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
}

核心只有四个字：

存、断、接、移

先保存：

next = cur->next;

然后反转：

cur->next = prev;

再移动：

prev = cur;
cur = next;

二十九、第三步：交替合并

现在有：

1 -> 2 -> 3
6 -> 5 -> 4

交替取：

1, 6, 2, 5, 3, 4

即可。

整个过程：

找中点：

O (n)

逆置：

O (n)

合并：

O (n)

所以：

O (n) + O (n) + O (n) = O (n)

额外空间只有几个指针：

O (1)

这就是站内 2019 真题给出的“三阶段算法”。(Any Docs)

三十、为什么2019这题特别重要？

因为它实际上把单链表三大核心算法一次性全考了：

快慢指针

链表逆置

链表合并

因此，本章最值得完整默写的一道算法题是：

2019 年这道题排第一。

三十一、2013 真题：两个升序链表合并成降序链表

题目：

两个长度分别为 $m, n$ 的升序链表，合并成一个长度为 $m + n$ 的降序链表。

问最坏时间复杂度。(Any Docs)

两个升序链表：

1 -> 4 -> 8
2 -> 3 -> 9

每次比较两个首结点。

取较小者后，可以采用头插法。

例如依次取：

1, 2, 3, 4, 8, 9

不断头插以后，结果自然反过来：

9, 8, 4, 3, 2, 1

每个结点最多访问一次：

O (m + n)

而：

max (m, n) \leq m + n \leq 2 max (m, n)

因此渐进意义下：

O (m + n) = O (max (m, n))

所以答案 D。(Any Docs)

三十二、这题又说明一个容易错的复杂度问题

很多同学看到：

m + n

就在选项中找

O (m + n)

找不到就慌。

要会判断渐进等价。

因为：

m + n = Θ (max (m, n))

所以：

O (m + n)

与

O (max (m, n))

在这里属于同一级。

三十三、静态链表

这部分真题很少，但模拟题有补充。

静态链表本质：

不用真正的指针，而是用数组下标表示“下一个结点的位置”。

例如：

typedef struct {
    DataType data;
    int link;
} SListNode;

如果结点 $i$ ：

S[i].link = 7;

意思就是：

下一个逻辑结点存储在

S [7]

。

因此模拟题问：

已知逻辑第 $k$ 个结点的数组下标为 $i$ ，第 $k + 1$ 个结点的数据是什么？(Any Docs)

答案：

S[S[i].link].data

而绝对不能写：

S[i+1].data

因为静态链表的：

逻辑相邻 \neq = 物理相邻

三十四、静态链表还可能考“备用链表”

站内模拟题还有一道：

主静态链表和空闲链表同时存在，删除主链表中的结点后，把释放位置头插到空闲链表中。(Any Docs)

本质就是同时完成两件事。

主链表中：

pre -> x -> next

删除：

pre -> next

随后把 $x$ 插到空闲链表：

avail -> oldFree

变：

avail -> x -> oldFree

所以静态链表不要觉得特殊。

它本质仍是：

链表，只不过指针变成数组下标

三十五、顺序表与链表复杂度判断题

站内模拟题问：

哪些操作可以在

O (1)

完成，其中正确答案是双向循环链表删除首个数据结点。(Any Docs)

为什么？

双向循环链表可以直接得到前驱、后继。

修改有限个指针即可：

O (1)

而只有头指针的普通单链表，如果要在末尾添加：

需要先找到尾结点：

O (n)

单向循环链表如果没有尾指针，要修改尾部关系，也可能需要遍历寻找尾结点：

O (n)

。

所以复杂度判断的核心不是：

“它是不是链表？”

而是：

当前给了哪些指针？能不能直接取得目标结点或其前驱？

三十六、第 2 章所有链表题，可以压缩成四种操作

以后遇到陌生链表算法，不妨先判断它本质属于哪种。

底层操作	典型题
找位置	倒数第 $k$ 个、中点、公共结点
改链接	插入、删除、移动结点
改方向	链表逆置
重组合	合并、拆分、交叉排列

2019 综合题就是：

找位置 + 拆分 + 改方向 + 重组合

所以复杂链表算法一般不是一种全新的算法，而是几个基础操作拼起来。

三十七、408链表算法题写代码的通用框架

假设带头结点：

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode;

以后可以把很多题理解成以下几类模板。

遍历

LNode *p = L->next;

while (p != NULL) {
    // process p
    p = p->next;
}

边遍历边删除

LNode *pre = L;
LNode *p = L->next;

while (p != NULL) {
    if (should_delete(p)) {
        pre->next = p->next;
        free(p);
        p = pre->next;
    } else {
        pre = p;
        p = p->next;
    }
}

逆置

LNode *pre = NULL;
LNode *p = head;

while (p != NULL) {
    LNode *q = p->next;
    p->next = pre;
    pre = p;
    p = q;
}

快慢指针

slow = first;
fast = first;

while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}

这四块最好达到不用思考就能写出来的程度。

三十八、链表算法最容易丢分的地方

第一类是丢后继。

例如错误：

p->next = pre;
p = p->next;

因为执行第一句后，

p->next

已经变成原来的前驱了。

原来的后继找不到。

所以一定提前：

q = p->next;

第二类是释放后继续访问。

错误：

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

p 已经释放。

正确做法应该提前保存后继，或者：

pre->next = p->next;
free(p);
p = pre->next;

第三类是头结点和首元结点混淆。

带头结点：

L -> a1 -> a2 -> ...

其中：

L

指向的是头结点，

真正的第一个元素是：

L->next

第四类是比较“数据相同”还是“结点相同”。

2012 公共后缀问题要求比较：

p = q

也就是地址相同。

不是：

p . d a t a = q . d a t a

否则两个不同位置恰好字符相同，也会被误认为公共结点。(Any Docs)

三十九、把整章真题按“算法思想”重新分类

这样复习会比按照教材目录背题更有效。

思想	对应站内真题
分段逆置	2010 数组循环左移
二分排除	2011 两个升序序列中位数
抵消法	2013 主元素
下标映射/原地哈希	2018 最小未出现正整数
多指针贪心	2020 三集合最小距离
链表归并+头插	2013 升序链表合成降序
地址追踪	2016 单链表内存布局
双链表修改	2016、2023
循环链表边界	2021
链表语句模拟	2024
前后指针间距	2009 倒数第 $k$ 个
尾端对齐	2012 公共后缀
辅助数组	2015 删除绝对值重复
找中点+逆置+交替合并	2019 链表重排

这些题基本已经覆盖了408线性表算法的主干。(Any Docs)

四十、一个非常重要的“条件 → 方法”映射

这是建议真正记住的东西。

看到：

有序

想到：

二分 / 双指针 / 归并

看到：

∣ d a t a ∣ \leq n

想到：

直接寻址 / 标记数组

看到：

额外空间 O (1)

想到：

原地交换 / 逆置 / 指针重连

看到：

倒数第 k 个

想到：

前后双指针

看到：

链表中点

想到：

快慢指针 1 : 2

看到：

两个链表公共尾部

想到：

长度差对齐

看到：

链表反向

想到：

保存 next 后改变 next

看到：

边遍历边删除

想到：

p r e + p

这比背20道题有价值。

四十一、可能出现的拓展考法

根据这些真题的命题方式，很容易进一步组合出新的算法题。

预测一：判断单链表是否中心对称

例如：

1 \to 2 \to 3 \to 2 \to 1

判断是否回文。

最优方法正好由2019真题变形而来：

找中点：

O (n)

逆置后半段：

O (n)

前后同时比较：

O (n)

所以：

T (n) = O (n)

S (n) = O (1)

这实际上就是2019题的：

找中点 + 逆置

少了最后的交替合并。

四十二、预测二：两个单链表是否相交

2012公共后缀题的直接变形。

如果两个无环单链表相交，那么从交点开始：

n e x t

链完全相同。

可以计算长度：

m, n

长链表先走：

∣ m - n ∣

随后同步前进。

若存在：

p = q

则相交。

复杂度：

O (m + n)

空间：

O (1)

。

四十三、预测三：删除链表倒数第 k 个结点

把2009年：

找倒数第 $k$ 个

与删除操作组合。

快指针先走 $k$ 或 $k + 1$ 步，让慢指针最终停在目标结点前驱。

然后：

q = slow->next;
slow->next = q->next;
free(q);

所以考研出题非常可能不是创造一个新算法，而是：

已有算法模板 + 一个基础操作

四十四、预测四：有序链表去重

例如：

1 \to 1 \to 2 \to 2 \to 3

变：

1 \to 2 \to 3

因为已经有序，所以相同元素必连续。

不需要2015题那样的辅助数组。

只需要比较：

p . d a t a

与：

p . n e x t . d a t a

时间：

O (n)

空间：

O (1)

这说明题目中的“有序”条件可以让算法发生巨大变化。

四十五、预测五：两个有序链表的交集

例如：

A : 1, 2, 4, 6

B : 2, 3, 4, 7

求：

2, 4

可以使用两个指针。

若：

A_{i} < B_{j}

移动 $A$ 。

若：

A_{i} > B_{j}

移动 $B$ 。

若相等：

记录并同时移动。

复杂度：

O (m + n)

这是2020年多数组指针思维与链表结构的组合。

四十六、本章算法题怎样分析时间复杂度？

链表特别容易被代码里的多个 while 吓到。

例如2019：

第一段：

O (n)

第二段：

O (n)

第三段：

O (n)

不是：

O (n^{3})

而是：

O (n) + O (n) + O (n) = O (n)

只有嵌套循环才通常乘起来。

例如：

for each p
    scan from beginning

才可能：

O (n^{2})

所以判断复杂度时先问：

这些循环是顺序执行还是嵌套执行？

四十七、本章考试优先级

如果现在准备408，本文将把这一章复习顺序排成下面这样：

单链表插入、删除、逆置必须完全掌握。
快慢指针必须掌握：中点、倒数第 $k$ 个。
2019链表重排完整掌握。
双链表插入删除语句必须会画图判断。
有序数组的双指针、二分思想必须掌握。
利用元素范围建立辅助数组/下标映射必须有敏感度。
静态链表理解即可，不值得投入与前几项相同的时间。

从站内收录的历年题来看，这个优先级也与真题覆盖非常吻合：顺序存储主要以算法题出现，而链式存储既有大量选择题，也反复出现完整算法设计题。(Any Docs)

四十八、最后把第 2 章压缩成一张“考场思维图”

遇到数组：

先看是否有序

有序：

\to 二分 / 双指针

无序但值域小：

\to 标记 / 下标映射

要求：

O (1) 空间

则：

\to 交换 / 逆置 / 原地调整

遇到链表：

先问：

目标是查找位置，还是修改结构？

找位置：

倒数第 $k$ 个：

\to 前后双指针

中点：

\to 快慢指针

公共结点：

\to 长度对齐

改结构：

删除：

\to 找前驱 + 跨过目标

插入：

\to 先保存旧链接，再修改

逆置：

\to 保存 next+ 反转 next

复杂重排：

\to 拆分成 “ 找中点、逆置、合并 ” 等基础动作

第 2 章真正需要形成的能力

如果学完这一章只是会说“顺序表随机访问 $O (1)$ ，链表插入 $O (1)$ ”，远远不够。

真正达到408要求，应该做到：

看到2010循环移位，能想到分段逆置；

看到2011两个有序数组，能意识到不能浪费有序性；

看到2013主元素，能想到抵消；

看到2015的

∣ d a t a ∣ \leq n

马上意识到值域可以映射为下标；

看到倒数第 $k$ 个，马上想到两个指针保持距离；

看到公共后缀，马上想到尾部对齐；

看到2019的

a_{1}, a_{n}, a_{2}, a_{n - 1}, \dots

能够自己拆成：

找中点 \to 逆置后半段 \to 交替合并

做到这一层，线性表的算法题基本就从“每一道都是新题”，变成了“几套模板的重新组合”。这也是这一章最重要的学习目标。(Any Docs)

数据结构第 2 章：线性表

On this page