链表¶

方法速览¶

任务	方法	口诀
链表 vs 数组	链表：不能随机访问、插删 O(1)；数组：随机访问 O(1)、插删要搬	数组点得出，链表走出去
头插法	新结点接旧头，头指针改指新	先接后改头
删除结点	要先拿到它的前驱	删除找前驱
双链表插入	先接新、后断旧	新的先挂，旧的再断
判环	快慢指针，fast 一步两格追 slow	快慢相遇必有环
反转	三指针 pre/cur/nxt 迭代	先存后继再掉头

链表与数组对比¶

随机访问：给下标 i 一步直达 a[i]——数组可以（地址连续，算一下就到），链表不行（结点散在内存各处，只能顺着 next 一个个走）。

操作	数组	链表
访问第 i 个元素	\(O(1)\) 随机访问	\(O(n)\) 顺着走
在已知位置插入/删除	\(O(n)\) 后面全体搬移	\(O(1)\) 改两个指针
大小	定义时固定	动态 new/delete
存储	连续一整块	结点散布 + 指针串联
额外开销	无	每个结点多一个指针域（8 字节）

例：单链表找第 3 个结点要走 3 步（head → 1 → 2 → 3）；数组直接 a[2]——“链表不具有的特点是可随机访问任一元素”是最高频真题。

增删改查（带头/不带头）¶

结点定义——后面所有函数都用它：

struct Node {
    int data;
    Node* next;
};

形参写成 Node*& head（指针的引用）：函数里要改 head 本身（头插、删首），值传递只改副本——引用直达本体。

增 ①：头插（新结点成为第一个）：

void pushFront(Node*& head, int val) {
    Node* s = new Node{val, head};   // ① 新结点接住旧头
    head = s;                        // ② 头指针改指新结点
}

顺序不能反：先改 head 会丢失整条旧链。

增 ②：尾插（新结点接到最后）：

void pushBack(Node*& head, int val) {
    Node* s = new Node{val, nullptr};
    if (head == nullptr) { head = s; return; }   // 空表：新结点就是头
    Node* p = head;
    while (p->next != nullptr) p = p->next;      // 走到最后一个
    p->next = s;                                 // 接上去
}

增 ③：按位插（第 i 位插入，i 从 1 数起）：

void insertAt(Node*& head, int i, int val) {
    if (i == 1) { pushFront(head, val); return; }   // 首位置 = 头插
    Node* p = head;
    for (int k = 1; k < i - 1 && p != nullptr; k++) // p 走到第 i-1 个（前驱）
        p = p->next;
    if (p == nullptr) return;                       // 位置越界
    Node* s = new Node{val, p->next};               // 新结点先接后继
    p->next = s;                                    // 前驱再接新结点
}

删：按位删（删除第 i 个——需要前驱）：

void eraseAt(Node*& head, int i) {
    if (head == nullptr) return;                    // 空表
    Node* p = head;
    if (i == 1) { head = head->next; delete p; return; }  // 删首：改 head
    for (int k = 1; k < i - 1 && p->next != nullptr; k++) // p 走到第 i-1 个
        p = p->next;
    Node* dead = p->next;
    if (dead == nullptr) return;                    // 位置越界
    p->next = dead->next;                           // 前驱跳过它
    delete dead;
}

单链表找前驱只能从头走——所以删除是“知位置仍要走”。

改：按位改（第 i 个的值改成 v）：

bool updateAt(Node* head, int i, int val) {
    for (int k = 1; k < i && head != nullptr; k++)  // 走到第 i 个
        head = head->next;
    if (head == nullptr) return false;              // 位置不存在
    head->data = val;
    return true;
}

查：按值找 / 按位取：

Node* findByValue(Node* head, int val) {   // 按值：返回结点指针
    for (; head != nullptr; head = head->next)
        if (head->data == val) return head;
    return nullptr;                        // 没找到
}

Node* atIndex(Node* head, int i) {         // 按下标：第 i 个（1 数起）
    for (int k = 1; k < i && head != nullptr; k++)
        head = head->next;
    return head;                           // 这就是“随机访问要走 i 步”
}

带头结点：在第一个数据结点前放一个不放数据的哑结点，head 永远指向它——上面所有函数的空表/首位置特判（pushBack、eraseAt 的 i==1 分支）都因此可以省掉。

对比	不带头	带头结点
空表判断	`head == nullptr`	`head->next == nullptr`
首位置插入/删除	要特殊处理（改 head 本身）	与其它位置逻辑统一
好处	省一个结点	代码无特判，不易错

双链表¶

每个结点有 prev 和 next 两个指针：找前驱 O(1)（单链表要 O(n)）。

在 p 之后插入 s（先接新、后断旧）：

s->next = p->next;        // ① s 先接右邻居
p->next->prev = s;        // ② 右邻居的 prev 指回 s
s->prev = p;              // ③ s 接左邻居 p
p->next = s;              // ④ 最后才断 p 的旧 next

关键：p->next 在 ④ 之前始终还是旧后继，所以 ①② 都靠它牵线——把 p->next = s 提前就会丢失右半条链。

循环链表¶

尾结点的 next 指回头（单循环）或头尾互指（双循环）：

判空：单循环看 head->next == head；
从任何结点出发都能走遍全表；
典型应用：约瑟夫环——围成一圈反复出列，天然用循环链表模拟。

快慢指针判环¶

Floyd 判圈：slow 一次走 1 步、fast 一次走 2 步：

有环：fast 终会在环里追上 slow（相遇）；
无环：fast 先走到 nullptr。

Node *slow = head, *fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;   // 相遇 → 有环
}
return false;                        // fast 到头 → 无环

延伸：相遇后把一个指针放回起点，两指针同速走，再次相遇处就是环的入口。快慢指针还能找中间结点：fast 到尾时 slow 恰在中点。

链表反转¶

三指针迭代（pre 已反转部分的尾，cur 当前，nxt 暂存后继）：

Node *pre = nullptr, *cur = head;
while (cur != nullptr) {
    Node* nxt = cur->next;   // ① 先存后继，防止掉头后丢失
    cur->next = pre;         // ② 掉头：指向前一个
    pre = cur;               // ③ pre 前进
    cur = nxt;               // ④ cur 前进
}
head = pre;                  // 循环结束 pre 是新头

例：1→2→3 反转过程表：

轮	cur	nxt	操作后指向
1	1	2	`1→null`，pre=1，cur=2
2	2	3	`2→1`，pre=2，cur=3
3	3	null	`3→2`，pre=3，cur=null 结束

结果 3→2→1，head 指向 3。

练习题目¶

练习 1 · 链表不具有的特点¶

题目

下列不是单链表特点的是（）

A. 插入删除不需要移动其他元素
B. 所需空间与表长成正比
C. 可以随机访问任一元素
D. 不必事先估计存储空间大小

答案与解析

答案：C

随机访问是数组的能力（算地址直达）；链表必须顺指针走，第 i 个要 i 步。

练习 2 · 访问第 i 个的代价¶

题目

长度为 n 的单链表，访问第 i 个结点（\(1 \le i \le n\)）的时间复杂度（）

A. \(O(1)\)
B. \(O(n)\) 无论 i 多少
C. \(O(i)\)
D. \(O(\log n)\)

答案与解析

答案：C

从头走 i 步，代价与 i 成正比；数组才是 O(1)。（若问“最坏情况”则答 \(O(n)\)，即 i = n。）

练习 3 · 数组做不到的¶

题目

与链表相比，数组做不到（或做不好）的是（）

A. 按下标直接访问
B. sizeof 求总大小
C. 连续存储
D. 已知位置处 O(1) 插入

答案与解析

答案：D

数组中间插入要把后面元素整体后移，O(n)；链表改两个指针 O(1)。

练习 4 · 头插法顺序¶

题目

不带头结点的链表，Node* s 要插到 head 之前成为新首结点，正确的是（）

A. head = s; s->next = head;
B. s->next = head->next; head = s;
C. s->next = head; head = s;
D. head = s; s->next = nullptr;

答案与解析

答案：C

先 s->next = head 接住旧链，再改 head。

干扰项思路：A 先改 head 会把旧链丢掉（s->next = s 自环）；B 漏掉了原首结点。

练习 5 · 头插法的序列¶

题目

依次头插 1、2、3（每次都插在最前），链表从头到尾是（）

A. 3 2 1
B. 2 3 1
C. 1 2 3
D. 1 3 2

答案与解析

答案：A

头插 = 每个新的都排最前：插 1 得 1；插 2 得 2 1；插 3 得 3 2 1——头插天然逆序。

练习 6 · 尾插法序列¶

题目

依次尾插 1、2、3，链表从头到尾是（）

A. 3 2 1
B. 3 1 2
C. 2 1 3
D. 1 2 3

答案与解析

答案：D

尾插保持输入顺序；与头插（逆序）对比记忆。

练习 7 · 删除需要前驱¶

题目

单链表中删除结点 p，必须先知道（）

A. p 的前驱
B. p 的后继
C. 链表尾结点
D. p 的下标

答案与解析

答案：A

删除就是让前驱跳过 p：pre->next = p->next；单链表结点自己不知道前驱是谁。（双链表则 p->prev 直接给出。）

练习 8 · 删除操作¶

题目

pre 指向结点 p 的前驱，删除 p 的语句（）

A. delete pre;
B. p = pre; delete p;
C. pre->next = p->next; delete p;
D. p->next = pre;

答案与解析

答案：C

前驱的 next 跨过 p，再释放 p。

练习 9 · 带头结点的好处¶

题目

设置头结点（哑结点）的主要好处是（）

A. 少用一个指针
B. 首位置的插入删除与其它位置逻辑统一，无需特判
C. 加快查找
D. 节省内存

答案与解析

答案：B

没有头结点时，删/插首元素要改 head 本身，代码要单独写；有了哑结点，所有位置都走“前驱跳过”同一套逻辑。

练习 10 · 判空条件¶

题目

带头结点的单链表判断“空表”的条件（）

A. head == nullptr
B. head == head->next->next
C. head->next == head
D. head->next == nullptr

答案与解析

答案：D

head 永远指向哑结点，哑结点后面没有数据结点才算空。

干扰项思路：A 是不带头结点的判空；C 是单循环链表的判空。

练习 11 · 遍历求长度¶

题目

求单链表长度必须（）

A. 用 sizeof 除以结点大小
B. O(1) 直接读
C. 读尾结点的 size 域
D. 从 head 走到 nullptr，边走边数

答案与解析

答案：D

链表没有“长度”域，sizeof 也只量得到单个结点；只能遍历计数，O(n)。

练习 12 · 双链表插入顺序¶

题目

在双向链表结点 p 之后插入 s，错误的操作序列是（）

A. s->next = p->next; p->next->prev = s; s->prev = p; p->next = s;
B. p->next = s; s->next = p->next; s->prev = p; p->next->prev = s;
C. A 是标准顺序，B 因 p->next = s 提前而失败
D. 两者都能正确完成插入

答案与解析

答案：B

p->next = s 一旦提前执行，p->next 不再是旧后继，后续 s->next = p->next 变成 s->next = s 自环。

练习 13 · 双链表找前驱¶

题目

双链表相对单链表的核心优势（）

A. 结点更小
B. 任一结点 O(1) 找到前驱
C. 不能判环
D. 只能头插

答案与解析

答案：B

prev 指针直接给前驱；单链表找前驱要从头走 O(n)。代价是每结点多一个指针（8 字节）。

练习 14 · 双链表删除¶

题目

双链表中删除结点 p（非头尾），正确的是（）

A. delete p->prev; delete p->next;
B. p->next = p->prev; delete p;
C. p->prev->next = p->next; p->next->prev = p->prev; delete p;
D. p = nullptr;

答案与解析

答案：C

前驱跨过 p、后继指回前驱，双向都接好再释放。

练习 15 · 单循环链表判空¶

题目

带头结点的单循环链表判空条件（）

A. head == nullptr
B. head->next == nullptr
C. head->next == head
D. head->prev == head

答案与解析

答案：C

空表时哑结点的 next 绕回自己；B 是普通单链表的判空，循环链表永远走不到 null。

练习 16 · 循环链表的遍历终点¶

题目

遍历带头结点单循环链表，循环应终止于（）

A. p == nullptr
B. 永不终止
C. p->next == nullptr
D. p == head

答案与解析

答案：D

绕一圈回到头即结束；空指针判据在循环链表里失灵（没有 next 为空的结点）。

练习 17 · 约瑟夫环¶

题目

n 人围圈报数出列（约瑟夫问题），最贴合的数据结构（）

A. 循环链表
B. 二叉树
C. 普通数组
D. 栈

答案与解析

答案：A

围成一圈 + 不断删除结点 = 循环链表天然模型；数到 m 删除、从下一人继续。

练习 18 · 判环原理¶

题目

Floyd 判圈用快慢指针能判环的原因（）

A. fast 每步都比 slow 多走，有环时 fast 会从后面追上 slow
B. fast 会先到达表尾
C. 慢指针会停下来
D. 环里结点更大

答案与解析

答案：A

环里两者速度差恒为 1 步，距离每轮缩小 1，必然相遇；无环时 fast 先撞 nullptr。

练习 19 · 快慢指针的实现¶

题目

判环循环里快指针的正确走法（）

A. fast = fast->next;
B. fast = fast->next->next;（配空指针检查）
C. fast = slow->next;
D. fast = fast->prev;

答案与解析

答案：B

一次两格；同时循环条件要检查 fast && fast->next 防止越空崩溃。

练习 20 · 找中间结点¶

题目

slow 一次走一步、fast 一次走两步（循环条件 fast != nullptr && fast->next != nullptr）。无环链表长度 \(n=4\)，循环结束时 slow 在（）

A. 第 1 个结点
B. 第 3 个结点（两个中间结点中的后者）
C. 第 2 个结点（两个中间结点中的前者）
D. 尾结点

答案与解析

答案：B

逐轮演算（结点编号 1~4）：

轮次	slow	fast
初值	\(1\)	\(1\)
第 1 轮	\(2\)	\(3\)
第 2 轮	\(3\)	空（越过表尾），循环结束

本写法下：偶数长度 slow 停在后一个中点（\(\lfloor n/2 \rfloor + 1\)，n=4 时是第 3 个）；奇数长度恰在正中（n=5 时 slow=3）。

干扰项思路：C 是另一种循环条件（while (fast->next && fast->next->next)，先多查一步再移动）的结果——两种模板答案差一位，做题以题面给出的循环为准。

练习 21 · 反转的第一步¶

题目

三指针反转循环里，Node* nxt = cur->next; 必须放在最前面的原因是（）

A. 语法规定
B. 一旦 cur->next = pre 掉头，原后继就被覆盖丢失
C. 让代码更快
D. 防止内存泄漏

答案与解析

答案：B

掉头操作会改写 cur->next，不先存后继，链的剩余部分就找不回来了。

练习 22 · 反转追踪¶

题目

1→2→3→nullptr 三指针反转结束后（）

A. 死循环
B. head 指向 1，链不变
C. head 指向 3，链为 3→2（1 丢失）
D. head 指向 3，链为 3→2→1→nullptr

答案与解析

答案：D

每轮掉一个头，最终 pre=3 成为新头，末结点（原头 1）的 next 是初始 pre=nullptr——恰好封尾。

练习 23 · 反转后原头结点¶

题目

反转后原来的首结点变成（）

A. 新的头结点
B. 尾结点，其 next 为 nullptr
C. 被删除
D. 悬空指针

答案与解析

答案：B

第一轮 cur(旧头)->next = pre = nullptr——旧头自然封尾。

练习 24 · 逆序输出不想改链¶

题目

不修改链表、按逆序输出所有结点值，可用（）

A. 栈（或递归）
B. 双指针交换
C. 队列
D. 直接下标倒着访问

答案与解析

答案：A

顺着走把值压栈，再弹栈输出即逆序；递归“走到尾再打印”是同一原理的系统栈版。

练习 25 · 复杂度总表¶

题目

长度 n 的单链表：定位到第 i 个后插入 / 从头查值 / 反转整表的时间复杂度分别为（）

A. \(O(n)\)、\(O(n)\)、\(O(n^2)\)
B. \(O(n)\)、\(O(1)\)、\(O(n)\)
C. \(O(1)\)、\(O(1)\)、\(O(n)\)
D. \(O(1)\)、\(O(n)\)、\(O(n)\)

答案与解析

答案：D

已定位则改指针 O(1)；查值最坏走全表；反转一遍循环 O(n)。

练习 26 · 存储开销¶

题目

64 位下单链表每个 int 结点 struct Node { int data; Node* next; } 的实际开销是（）

A. \(4\) 字节
B. \(8\) 字节
C. \(16\) 字节（对齐后）
D. \(12\) 字节

答案与解析

答案：C

数据 4 + 指针 8 = 12，对齐到最大成员 8 的倍数 → 16——链表的“指针域开销”不是小数。

历年真题¶

2019 年 · 第 6 题¶

题目

链表不具有的特点是（）。

A. 所需空间与线性表长度成正比
B. 插入删除不需要移动元素
C. 可随机访问任一元素
D. 不必事先估计存储空间

答案与解析

答案：C

随机访问（按下标直达）是数组的专利；链表结点散布、靠指针串联，访问第 i 个必须从头走 i 步。

2020 年 · 第 7 题¶

题目

链表不具有的特点是（）。

A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比

答案与解析

答案：A

同一考点两年连考：选项顺序换了，“随机访问”仍是链表没有的能力。

2022 年 · 第 4 题¶

题目

链表和数组的区别包括（）。

A. 数组不能排序，链表可以
B. 链表比数组能存储更多的信息
C. 数组大小固定，链表大小可动态调整
D. 以上均正确

答案与解析

答案：C

数组编译期定长，链表靠 new/delete 动态增减。A 显然错（数组当然能排序）；B 错在“存更多信息”——存多少取决于内存，与结构无关。

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

标准顺序“先接新、后断旧”：

步	语句	作用
1	`s->next = p->next`	s 接住旧后继
2	`p->next->prev = s`	旧后继的 prev 指回 s
3	`s->prev = p`	s 接住 p
4	`p->next = s`	最后才改 p 的 next

干扰项思路：A 第 3 步先执行 p->next = s，第 4 步 s->next = p->next 变成自环；B 同病；C 的第 4 步 p->next->prev = s 在 p->next = s 之后——改的是 s 自己的 prev，旧后继的 prev 没人改。

易错小结¶

链表不能随机访问（2019/2020 两年原题）：第 i 个要走 i 步——数组才有 O(1) 下标直达；
头插先 s->next = head 再 head = s，顺序反了丢整条链；头插序列是逆序；
删除要前驱；单链表找前驱 O(n)，双链表 O(1)；
带头结点：首位置无特判、判空看 head->next；
双链表插入“先接新、后断旧”：p->next = s 永远最后做；
快慢指针：fast 两步 slow 一步，相遇有环；找中点要分奇偶；
反转先存 nxt = cur->next 再掉头；旧头自动封尾。