第 53 章链式连接——链表入门

🏗️ 前情回顾：第 51 章你用 stack 解决了括号匹配，第 52 章你用 vector 管理了"能自动伸缩"的动态数组。它们各有优势——vector 在末尾加元素飞快，stack/queue 按规则取元素效率极高。但你有没有发现一个问题？如果要在 vector 的中间插入（或删除）一个元素，后面的所有元素都得整体移动——当数据量达到十万级时，这个"搬运"代价相当可观。有没有一种结构，插入删除不需要"整体搬家"？有——这就是本章的主角：链表。

🎯 本章目标

学完这一章，你能：

说出链表和数组在内存布局上的本质区别
定义链表节点（data + next 指针）
实现单链表的插入、删除、遍历操作
理解双向链表和循环链表的基本概念
用数组模拟链表（竞赛常用技巧）
根据场景选择合适的线性结构

📖 故事引入

场景：火车车厢连接

一列火车由许多节车厢组成。你想在中间加一节车厢怎么办？把后面所有车厢解开 → 挂上新车厢 → 把后面车厢重新挂到新车厢后面。不需要移动后面所有车厢的位置，只需要改两个连接扣。

反过来，你想拆掉中间一节车厢？把它的前扣和后扣解开，把前后车厢直接连起来——也是改两个连接扣。

链表就是数据世界的"火车"：每个节点是一节车厢，指针是连接扣。

另一种比喻：寻宝游戏

小明参加寻宝游戏，第一个宝箱里放着一张纸条："下一个宝箱在花园"。你跑到花园，第二个宝箱里又有一张纸条："下一个宝箱在图书馆"……你不需要提前知道所有宝箱的位置，只需要跟着线索走。

链表就是这样的"线索链"——每个节点知道下一个节点在哪，跟着 next 指针一趟走到底是终点。

🧱 知识讲解

53.1 数组 vs 链表：内存里的两种排法

数组在内存里是连续的——所有元素像连排别墅一样紧挨着。链表在内存里是离散的——每个节点可以在任何位置，通过指针"串"起来。

对比维度	数组 / vector	链表
内存布局	连续排列	离散分布，用指针连接
访问第 k 个元素	O(1) 直接跳	O(n) 沿链走到第 k 个
在中间插入	O(n) 需要整体搬家	O(1) 只需改两个指针
在中间删除	O(n) 需要整体搬家	O(1) 只需改一个指针
额外内存开销	无	每个节点多一个 `next` 指针

一句话：频繁随机访问用数组，频繁插入删除用链表。

53.2 单链表：节点的定义

每个节点包含两部分：数据和指向下一个节点的指针。

cpp

struct Node {
    int data;       // 数据域：存什么值
    Node* next;     // 指针域：指向下一个节点（Node 类型）
};  // ← 别忘了分号！

注意 Node* next 的类型是 Node*——指针指向另一个 Node。这就是链表的核心：结构体自己包含指向同类型结构体的指针，从而把节点串成一条链。

创建节点和连接：

cpp

Node* head = new Node;  // 创建头节点（用 new 在堆上分配）
head->data = 10;
head->next = nullptr;   // 目前只有它自己

Node* second = new Node;
second->data = 20;
second->next = nullptr;

head->next = second;    // 头节点指向第二个 → 链形成了！

// 再插入一个节点到中间（10 和 20 之间）
Node* mid = new Node;
mid->data = 15;
mid->next = head->next; // 新节点先指向 20
head->next = mid;        // 10 的 next 改指向新节点
// 现在链：10 → 15 → 20

💡 new 在"堆"（heap）上分配内存，返回的是指针。这块内存在程序结束前一直存在（除非用 delete 手动释放）。和普通变量不同——普通变量出大括号就自动销毁，new 出的不销毁。

53.3 遍历链表

顺着 next 指针一路走下去，直到遇到 nullptr：

cpp

void printList(Node* head) {
    Node* cur = head;        // cur 从头部开始走
    while (cur != nullptr) { // 没走到末尾就继续
        cout << cur->data << " ";  // 输出当前节点的值
        cur = cur->next;           // 走一步：cur 指向下一个
    }
    cout << endl;
}

动画演示：

cur → [10|●] → [15|●] → [20|×]
输出 10，cur 走到下一个
cur → [10|●] → [15|●] → [20|×]
输出 15，cur 走到下一个
cur → [10|●] → [15|●] → [20|×]
输出 20，cur 变成 nullptr → 循环结束

53.4 链表基本操作

（1）在头部插入

cpp

void insertHead(Node*& head, int val) {
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = head;  // 新节点的 next 指向原来的头
    head = newNode;        // 头指针更新为新节点
}
// 注意：head 用了引用 Node*&，这样修改 head 才会影响到外部

（2）在尾部插入

cpp

void insertTail(Node*& head, int val) {
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = nullptr;

    if (head == nullptr) {   // 链表为空 → 新节点就是头
        head = newNode;
        return;
    }

    Node* cur = head;
    while (cur->next != nullptr) {  // 走到最后一个节点
        cur = cur->next;
    }
    cur->next = newNode;     // 最后一个节点指向新节点
}

（3）删除指定值的第一个节点

cpp

void deleteNode(Node*& head, int val) {
    if (head == nullptr) return;   // 空链表，不删

    if (head->data == val) {       // 要删的是头节点
        Node* temp = head;
        head = head->next;         // 头指针后移
        delete temp;               // 释放内存
        return;
    }

    Node* cur = head;
    while (cur->next != nullptr && cur->next->data != val) {
        cur = cur->next;           // 找到目标节点的前一个
    }
    if (cur->next != nullptr) {
        Node* temp = cur->next;
        cur->next = cur->next->next;  // 跳过目标节点
        delete temp;
    }
}

53.5 双向链表：前后都能走

单链表只能往后走——如果你在中间某个节点，想知道它的前一个节点是谁，得从头再走一遍。双向链表解决了这个问题：每个节点多一个 prev 指针，指向前一个节点。

cpp

struct DNode {
    int data;
    DNode* prev;  // 前驱指针
    DNode* next;  // 后继指针
};

双向链表的优势：可以从任意位置往前或往后遍历，删除某个节点时不需要"找前驱"（通过 prev 直接拿到）。代价是每个节点多一个指针，内存开销翻倍。

53.6 循环链表：首尾相连

普通链表的最后一个节点的 next 是 nullptr。如果把最后一个节点的 next 指向头节点，就形成了循环链表——永远走不到尽头，就像小朋友手拉手围成一个圈。

循环链表最经典的应用是约瑟夫问题：N 个人围成一圈，从第 K 个人开始报数，报到 M 的人出列，下一个人继续报数……用循环链表模拟非常自然。

cpp

// 约瑟夫问题（循环链表版）
int josephus(int n, int m) {
    // 1. 创建循环链表：1 → 2 → ... → n → 回到1
    Node* head = new Node{1, nullptr};
    Node* cur = head;
    for (int i = 2; i <= n; i++) {
        cur->next = new Node{i, nullptr};
        cur = cur->next;
    }
    cur->next = head;  // 最后一个指向头 → 成环

    // 2. 每次数 m 步，删除一个节点
    while (cur->next != cur) {  // 只剩一个节点时停止
        for (int i = 1; i < m; i++) {
            cur = cur->next;    // 走 m-1 步（站在要删节点的前面）
        }
        Node* temp = cur->next;
        cur->next = temp->next; // 跳过要删的节点
        delete temp;
    }
    int result = cur->data;
    delete cur;
    return result;
}

💡 约瑟夫问题也可以用第 51 章学的 queue 解决，效率更高。链表的优势在于直观。——实际上，竞赛中用循环链表做约瑟夫还不如用 queue 或数学公式，但理解链表结构本身才是目的。

53.7 数组模拟链表（竞赛常用技巧）

在竞赛中，真正用 new/delete 来操作链表指针的代码其实不多——因为频繁的 new 和 delete 慢，而且容易写出 bug。竞赛选手更常用数组模拟链表：用两个数组 data[] 和 next[] 取代指针，用数组下标"模拟"地址。

cpp

const int MAXN = 100005;
int data[MAXN];    // 存节点的值
int nxt[MAXN];     // nxt[i] 是节点 i 的下一个节点的下标
int head = -1;     // 头节点的下标，-1 表示空
int tot = 0;       // 已使用的节点数

// 在头部插入
void insertHead(int val) {
    data[tot] = val;
    nxt[tot] = head;  // 新节点的 next 指向原头
    head = tot;       // 头更新为新节点
    tot++;
}

// 遍历
void printList() {
    for (int i = head; i != -1; i = nxt[i]) {
        cout << data[i] << " ";
    }
    cout << endl;
}

数组模拟链表的三个好处：

不需要 new/delete，速度快
不会出现"内存泄漏"（忘记 delete）
调试时可以看到所有节点的值（而真正的指针地址你肉眼读不懂）

竞赛选手称之为"静态链表"——用数组的静态空间模拟指针的动态连接。熟悉这个技巧后，链表题目写起来反倒比用指针版更顺手。

53.8 链表的优缺点总结

优点：

插入删除 O(1)（如果已经定位到插入/删除位置）
不需要连续内存空间，空间利用率灵活
动态扩容不需要"整体搬家"

缺点：

随机访问 O(n)，不能像数组那样 a[i] 直接跳
每个节点多一个指针（额外内存开销）
无法利用 CPU 缓存（数据不连续，缓存命中率低）

💡 实际开发中，vector 和 list（STL 内置链表）都提供了。大多数场景 vector 更快（CPU 缓存友好），只有明确需要大量中间插入删除时才用链表。

✋ 动手试试

试试 1：用 struct Node 创建 5 个节点（值为 1~5），手动用 next 指针连成链表，然后遍历输出。

试试 2：在上面的链表基础上，写一个 insertAfter(Node* node, int val) 函数——在给定节点后面插入新节点。

试试 3：写一个 reverseList(Node*& head) 函数，将单链表反转。例如 1→2→3→4 变成 4→3→2→1。（提示：用三个指针 cur、prev、next 逐步翻转。）

试试 4：用数组模拟链表的方式，实现约瑟夫问题（N=41, M=3，问最后剩下的人是第几个）。答案应该是 31。

⚠️ 容易犯的错

错 1：操作空链表时忘记判空

❌ head->next = newNode; // 如果 head 是 nullptr，直接崩

✅ if (head == nullptr) { head = newNode; return; }

错 2：更新指针顺序搞反

❌ 插入节点时：

cpp

head->next = newNode;  // 先断了原链接
newNode->next = head->next;  // 此时 head->next 已经是 newNode 了！错误！

✅ 正确顺序：先让新节点指向后继，再让前驱指向新节点。

cpp

newNode->next = head->next;  // 第一步
head->next = newNode;        // 第二步

错 3：`new` 了但忘记 `delete`

❌ 用 new 创建了一大堆节点，从不 delete → 内存泄漏

✅ 删除节点时记得 delete temp;，写一个 clearList(head) 函数统一释放。

错 4：遍历条件写成 `while (cur->next != nullptr)`

❌ 最后一个节点会被漏掉

✅ 遍历应该用 while (cur != nullptr)。只有当你的逻辑是"停在最后一个节点不动"时才用 cur->next != nullptr。

📝 练习

基础题

1. 填空题

（1）链表的每个节点包含两个部分：____ 和 ____。

（2）单链表的最后一个节点的 next 指针指向 ____。

（3）双向链表比单链表多一个 ____ 指针。

（4）循环链表的特征是最后一个节点的 next 指向 ____。

（5）数组模拟链表用 ____ 代替 Node*，用两个数组 data[] 和 next[] 实现。

2. 读代码写结果

cpp

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};
head = head->next;
Node* cur = head;
while (cur != nullptr) {
    cout << cur->data << " ";
    cur = cur->next;
}

输出是什么？

提高题

3. 编程题 — 链表去重

给定一个有序单链表的头指针，删除所有重复的元素（保留一个）。例如 1→1→2→3→3 变为 1→2→3。

（提示：遍历链表，如果 cur->data == cur->next->data，就跳过 cur->next。）

4. 编程题 — 合并两个有序链表

给定两个递增有序的单链表 L1 和 L2，将它们合并成一个新的递增有序链表。例如 1→3→5 和 2→4→6 合并为 1→2→3→4→5→6。

（提示：类似归并排序的合并步。用"双指针"分别遍历两个链表，每次取较小的节点接到新链表后面。）

挑战题

5. 编程题 — 判断链表是否有环

给定一个单链表，判断它是否包含环（即某个节点的 next 指向了链表中之前的节点，形成循环）。如果有环，输出环的入口节点的值。

（提示：经典解法——快慢指针。快指针每次走两步，慢指针每次走一步。如果有环，它们一定会相遇。相遇后，再让一个指针从头开始和慢指针同步走，相遇点就是环入口。这个技巧称为 Floyd 判圈算法。）

6. 编程题 — 链表实现大整数加法

用链表表示两个非负整数（每一位是一个节点，头节点是个位）。写函数将两个链表表示的数相加，返回一个新的链表。

例如：3→4→2（表示 243） + 5→6→4（表示 465） = 8→0→7（表示 708）。

（提示：模拟竖式加法——同时遍历两个链表，逐位相加并处理进位。）

🧠 本章小结

链表 vs 数组：
    数组：连续内存 → 随机访问 O(1)，中间插入删除 O(n)
    链表：离散内存 → 随机访问 O(n)，中间插入删除 O(1)

单链表节点：struct Node { int data; Node* next; };
遍历：while (cur != nullptr) { cur = cur->next; }
插入：先让新节点指向后继，再让前驱指向新节点
删除：让前驱跳过目标节点，然后 delete

双向链表：多一个 prev 指针，前后都能走
循环链表：尾部 next 指向头部，首尾相连

数组模拟链表（竞赛常用）：
    data[tot] / nxt[tot] → 用下标代替指针，更快更稳

📝 配套练习

共3题。链表在竞赛中用数组模拟——只配核心题，更多应用留给下册数据结构。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1160	https://hydro.ac/p/luogu-P1160	数组模拟双向链表、插入删除
◆ 拓展	luogu-P1996	https://hydro.ac/p/luogu-P1996	链表版约瑟夫环
◆ 拓展	luogu-P1563	https://hydro.ac/p/luogu-P1563	环形链表思想、玩具谜题

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 2 道◆拓展题，覆盖不同变式和细节。

配套练习

共3题。链表在竞赛中用数组模拟——只配核心题，更多应用留给下册数据结构。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1160	https://hydro.ac/p/luogu-P1160	数组模拟双向链表、插入删除
◆ 拓展	luogu-P1996	https://hydro.ac/p/luogu-P1996	链表版约瑟夫环
◆ 拓展	luogu-P1563	https://hydro.ac/p/luogu-P1563	环形链表思想、玩具谜题

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 2 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能画出单链表的内存示意图（节点用方块，next 用箭头）
[ ] 我会定义链表节点结构体并创建节点
[ ] 我能写出链表的遍历、头部插入、尾部插入代码
[ ] 我理解插入时指针修改的顺序（先连后继，再改前驱）
[ ] 我知道双向链表比单链表多了什么
[ ] 我能解释循环链表和约瑟夫问题的关系
[ ] 我会用数组模拟链表写出基本操作
[ ] 我知道链表 vs 数组各自的适用场景

🚀 下章预告

链表解决的是"数据怎么串起来"的问题。接下来我们换个方向，走进一个完全不同的世界——数字的秘密。为什么质数这么重要？RSA 加密为什么安全？一个数有多少个约数？下一章开启上册最后一块拼图：初等数论——让你领略数学在算法中的魔力。

第 53 章 链式连接——链表入门 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

53.1 数组 vs 链表：内存里的两种排法 ​

53.2 单链表：节点的定义 ​

53.3 遍历链表 ​

53.4 链表基本操作 ​

53.5 双向链表：前后都能走 ​

53.6 循环链表：首尾相连 ​

53.7 数组模拟链表（竞赛常用技巧） ​

53.8 链表的优缺点总结 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：操作空链表时忘记判空 ​

错 2：更新指针顺序搞反 ​

错 3：new 了但忘记 delete ​

错 4：遍历条件写成 while (cur->next != nullptr) ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​

🚀 下章预告 ​