第2章线性表（自学版）¶

章节定位：高频基础章

这一章是后续链式结构、栈队列、查找和排序代码理解的共同基础。
建议把顺序表、单链表、双链表和典型综合题连在一起看，并配合代码专题同步对照。

适用原文：DS.pdf 第 24-73 页
配套真实代码：第2章普通代码版

这一章是整本书里最“会反复考、反复用、反复变形”的基础章之一。

如果说第 1 章是在搭概念地基，那么第 2 章就是第一次真正开始“落手写结构、写操作、分析复杂度”。

先明确一个原则：

书里的很多代码偏“算法表达”
我这里会尽量把核心伪代码补成可运行的 C 代码
代码不是只看思想，而是尽量做到真的能作为模板使用

1. 本章定位¶

1.1 本章讲什么¶

本章研究的是最基础、最典型的一类结构：

线性表

所谓线性表，本质上就是：

一组数据排成一条线
每个元素最多只和前后元素发生直接关系

这一章主要回答三个问题：

线性表到底是什么
线性表怎么存
线性表的常见操作怎么写、怎么分析复杂度

1.2 为什么这一章特别重要¶

因为后面很多结构，都是在和它比较：

栈、队列，本质上都可以看成“受限制的线性表”
串，本质上可以看成元素类型受限的线性表
很多查找、排序算法，也经常默认对象是顺序表

所以这一章不只是“学一个结构”，而是在学：

如何定义结构
如何选存储方式
如何写基本操作
如何分析这些操作的性能

1.3 学完本章后你应该会什么¶

准确说出线性表的定义和特点
区分线性表、顺序表、链表三个概念
写出顺序表的初始化、插入、删除、查找
写出带头结点单链表的初始化、插入、删除、查找
理解头插法、尾插法、逆置、双指针这些常见技巧
根据场景判断顺序表和链表谁更合适

2. 本章结构总览¶

原书这一章的大结构可以整理成：

2.1 线性表的定义和基本操作
2.2 线性表的顺序表示
2.3 线性表的链式表示
归纳总结
思维拓展

更进一步按学习主线来看，其实就两大块：

2.1 先搞清楚“线性表是什么”¶

核心是逻辑层：

有限序列
相同数据类型
一对一的相邻关系

2.2 再搞清楚“线性表怎么实现”¶

核心是实现层：

顺序表：用数组思想来存
链表：用结点和指针来连

真正需要反复吃透的，不是定义，而是：

插入
删除
查找
构造
复杂度

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

3.1 线性表的定义¶

原书核心意思：

线性表是具有相同数据类型的 n(n>=0) 个数据元素的有限序列。

这句话非常经典，也非常高频。

建议你直接拆开理解：

3.1.1 相同数据类型¶

线性表中的元素类型要一致。

比如：

[3, 5, 7, 9] 可以看成一个整数线性表
[张三, 李四, 王五] 可以看成一个字符串线性表

但像：

[3, "张三", true]

这种就不符合这里教材语境下的标准线性表定义。

3.1.2 有限¶

线性表的元素个数是有限的。

这点看起来像废话，但它是在告诉你：

线性表是一个“可完整描述、可完整处理”的结构

3.1.3 序列¶

“序列”是关键。

它强调：

元素之间有先后顺序
不是乱堆在一起

所以线性表不是“集合”。

集合只关心“有哪些元素”，不关心顺序；线性表既关心“有哪些元素”，也关心“谁在谁前面”。

3.1.4 逻辑特征¶

原书强调：

除第一个元素外，每个元素有且仅有一个直接前驱
除最后一个元素外，每个元素有且仅有一个直接后继

这句话你可以理解成：

整条表像一根链条
每个普通结点都夹在前后两个结点之间
两端例外，一个没前驱，一个没后继

3.1.5 线性表的几个关键特点¶

原书这一节可以整理成下面几条：

元素个数有限
元素之间有逻辑顺序
每个元素都是单个数据元素
元素类型相同
讨论的是逻辑关系，不关心元素实际含义

这一点很重要：

线性表是逻辑结构，不是具体实现。

所以一定不要混淆：

线性表：逻辑结构
顺序表、链表：存储结构

3.2 线性表的基本操作¶

原书这一节其实是在给后面整个章节定接口。

可以把它理解成：

无论你是顺序表还是链表
最终都要支持这些核心操作

常见基本操作包括：

初始化表 InitList
求表长 Length
按值查找 LocateElem
按位查找 GetElem
插入 ListInsert
删除 ListDelete
输出 PrintList
判空 Empty
销毁 DestroyList

这里的一个学习重点是：

相同的操作接口，在不同存储结构下，代码实现和性能都可能不同。

3.3 本节自查题的核心结论¶

结论 1¶

线性表中的元素是：

数据元素

不是：

数据项

结论 2¶

“100 个字符组成的序列”是线性表； “所有整数组成的序列”不是线性表，因为它不是有限的。

结论 3¶

非空线性表中，如果一个元素既没有前驱也没有后继，那么：

说明整个表只有 1 个元素

4. 2.2 线性表的顺序表示¶

这一节是整章第一块真正“能写代码”的地方。

4.1 顺序表到底是什么¶

原书核心意思：

顺序表就是线性表的顺序存储表示
用一组地址连续的存储单元依次存放线性表中的元素

白话解释：

逻辑上挨着的元素，在内存里也尽量挨着放

最像什么？

像一排连续座位
第 1 个、第 2 个、第 3 个，物理位置也是连着的

4.1.1 顺序表的关键特性¶

逻辑顺序和物理顺序一致
可以随机访问
按位置访问快
插入删除可能慢

4.1.2 为什么它能随机访问¶

因为第 i 个元素的位置可以直接算出来。

这就是为什么：

按位查找通常是 O(1)

它不是一个一个往后找，而是直接跳过去。

4.2 顺序表的两种分配方式¶

原书这里讲了两种：

静态分配
动态分配

4.2.1 静态分配¶

特点：

一开始就开好固定大小的数组
空间不够时没法自动扩

优点：

简单

缺点：

不灵活
容量写死

4.2.2 动态分配¶

特点：

运行时申请空间
不够时可以扩容

注意：

动态分配不等于链式存储。

这一点非常容易误解。

它仍然是顺序存储，因为：

本质上还是一段连续空间

只不过这段连续空间的大小可以在运行时调整。

4.3 顺序表真实代码¶

书里的写法偏伪代码，我已经补成了真实 C 代码，文件在：

第2章普通代码版

顺序表部分已经包含这些可运行函数：

InitSeqList
DestroySeqList
EnsureSeqListCapacity
SeqListInsert
SeqListDelete
SeqListGetElem
SeqListLocateElem
SeqListEmpty
SeqListLength
PrintSeqList

4.3.1 顺序表结构体¶

typedef struct {
    ElemType *data;
    int length;
    int capacity;
} SeqList;

这比书里的伪代码更完整，因为这里补齐了动态顺序表最常用的三个字段：

data：指向数组
length：当前元素个数
capacity：当前容量

4.3.2 初始化为什么要传初始容量¶

因为真实代码里不能只说“给它分配空间”。

你得明确：

初始分配多少
分配失败怎么办

这就是教材伪代码和真实工程代码最重要的差别之一。

4.3.3 插入操作的真实理解¶

顺序表插入本质上分两步：

先挪位置，腾出空位
再把新值放进去

如果在第 pos 个位置插入，那么：

从表尾开始往后挪
一直挪到 pos

为什么要“从后往前”挪？

因为如果从前往后挪，会把原数据覆盖掉。

4.3.4 删除操作的真实理解¶

顺序表删除本质上是：

记住要删的值
后面的元素整体向前补位

所以顺序表的删除慢，不是因为“删除”这个动作本身慢，而是因为“补位”要移动很多元素。

4.3.5 顺序表复杂度总结¶

按位访问¶

时间复杂度：O(1)

按值查找¶

最好：O(1)
最坏：O(n)
平均：O(n)

插入¶

表尾插入最好：O(1)
表头插入最坏：O(n)
平均：O(n)

删除¶

删尾最好：O(1)
删头最坏：O(n)
平均：O(n)

4.3.6 顺序表什么时候适合用¶

适合：

经常按位置访问
元素数量变化不太剧烈

不太适合：

频繁在中间插入删除

5. 2.3 线性表的链式表示¶

顺序表的核心问题是：

插入删除时移动元素太贵

所以链表出现了。

5.1 单链表的核心思想¶

单链表不要求元素在物理上连续存放。

它的做法是：

每个结点除了存数据
还存下一个结点的位置

也就是：

用“指针”把离散的结点串起来

5.1.1 单链表结点¶

真实代码结构：

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

这就是书里最经典的单链表结点定义。

5.1.2 头指针和头结点¶

这两个概念一定要分清。

头指针¶

永远指向链表的第一个结点位置
它是“进入链表”的入口

头结点¶

是人为额外加的一个结点
不一定存有效数据
主要为了让操作统一

带头结点的好处非常大：

在第一个位置插入/删除时，不用特殊处理
空表和非空表的代码风格更统一

后面如果不特别说明，我默认都按：

带头结点单链表

来讲。

5.2 单链表真实代码¶

我已经把书里常用伪代码补成了真实 C 版本，文件还是：

第2章普通代码版

已经补好的函数包括：

InitLinkList
DestroyLinkList
LinkListLength
LinkListGetElem
LinkListLocateElem
LinkListInsert
LinkListDelete
BuildLinkListHeadInsert
BuildLinkListTailInsert
ReverseLinkList
PrintLinkList

5.2.1 链表初始化¶

真实代码里，初始化不是一句“令头指针为空”就够了。

如果采用带头结点方案，就需要：

申请头结点空间
让 head->next = NULL

5.2.2 按位查找¶

链表不能随机访问。

这意味着：

想找第 i 个元素
必须从头往后一个一个走

所以复杂度通常是：

O(n)

5.2.3 插入操作的本质¶

单链表插入真正做的，不是移动元素，而是“改链接”。

在第 i 个位置插入，本质上是：

先找到第 i-1 个结点
新结点的 next 指向原来的后继
前驱结点的 next 指向新结点

顺序不能反。

如果反了，就容易把链断掉。

5.2.4 删除操作的本质¶

删除第 i 个结点，本质上是：

找到它的前驱
让前驱跨过它，直接连到它后面
释放被删结点

所以链表删除的优势在于：

不需要整体搬家

但代价是：

你得先找到前驱

5.2.5 头插法和尾插法¶

这是链表构造题特别高频的两个技巧。

头插法¶

每来一个结点，就插到链表最前面。

特点：

写法短
容易实现
会把输入顺序反过来

尾插法¶

每来一个结点，就接到链表最后面。

特点：

能保持原顺序
要维护尾指针更方便

5.2.6 链表逆置¶

逆置是单链表最经典的基本功之一。

代码采用的是“迭代逆置”：

核心思想：

每次摘下当前结点
头插到新链表前面

这其实就是：

用不断改指针的方式，把方向整体反过来

5.3 顺序表 vs 单链表¶

这一节是本章最应该形成的判断力。

维度	顺序表	单链表
存储方式	连续空间	离散结点 + 指针
按位访问	快，`O(1)`	慢，`O(n)`
插入删除	常慢，常需移动元素	找到位置后改指针较方便
存储密度	高	较低，要额外存指针
空间要求	需要连续空间	不要求连续空间

一句话记忆：

经常随机访问，用顺序表
经常插删结构，用链表

6. 本章前半部分必须掌握的代码思想¶

到目前为止，这一章你最该真正掌握的，不是名词，而是下面这些代码动作：

顺序表插入时“从后往前搬”
顺序表删除时“从前往后补”
单链表插入时“先接后面，再改前面”
单链表删除时“先找前驱，再跳过目标”
头插法会逆序
尾插法保序
单链表按位查找必须遍历

7. 本章当前代码化进度¶

因为你特别强调“不要停在伪代码”，我这里也明确下当前已经补成真实代码的部分。

已补成真实 C 代码¶

顺序表核心结构
动态顺序表初始化
扩容
插入
删除
按位查找
按值查找
打印
带头结点单链表初始化
单链表插入
单链表删除
头插法建表
尾插法建表
单链表逆置

尚未完全代码化但已进入提取范围¶

循环链表
双链表
静态链表
本章后半部分综合算法题

这些我会在继续推进第 2 章时接着补成真实代码。

8. 本章当前复习提纲¶

8.1 一句话主线¶

线性表先学“是什么”，再学“怎么存”，最后学“怎么高效地改和查”。

8.2 必背结论¶

线性表是逻辑结构
顺序表和链表是存储结构
顺序表按位访问快
链表插删更灵活
动态分配的顺序表仍然是顺序存储

8.3 必会代码动作¶

顺序表插入
顺序表删除
单链表插入
单链表删除
头插法
尾插法
逆置

9. 这一稿说明¶

这里先给出第 2 章最核心、最需要“真代码”的骨架，并配套真实 C 实现。

对你现在最直接有用的文件有两个：

讲解稿：本书第2章正文
代码稿：第2章普通代码版

后续继续补第 2 章时，我会优先做两件事：

把链式表示后半段和本章综合题继续补全
继续把原书伪代码替换成可以直接运行的 C 代码

10. 伪代码与真实代码对照¶

你特别强调“不要只给伪代码”，这一节就专门把原书伪代码和可运行代码放在一起对照。

说明：

左边是根据原书内容整理后的伪代码写法
右边是真实可运行的 C 代码思路
两边都会带注释

这样你可以同时学到：

书上算法思想是怎么表达的
真代码为什么要比伪代码多出边界检查、内存管理和注释

10.1 顺序表初始化：伪代码 vs 真代码¶

原书伪代码（整理版）：

// 动态顺序表初始化
void InitList(SeqList &L) {
    L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
    L.length = 0;          // 当前长度为 0
    L.MaxSize = InitSize;  // 记录容量
}

真实代码（可运行 C 版）：

/* 初始化动态顺序表，并分配初始连续空间。 */
bool InitSeqList(SeqList *list, int init_capacity) {
    if (list == NULL || init_capacity <= 0) {
        return false;  /* 参数非法，直接失败 */
    }

    list->data = (ElemType *)malloc(sizeof(ElemType) * init_capacity);
    if (list->data == NULL) {
        return false;  /* 内存申请失败 */
    }

    list->length = 0;           /* 当前没有元素 */
    list->capacity = init_capacity; /* 记录当前容量 */
    return true;
}

关键差别：

伪代码默认内存一定申请成功
真代码必须检查空指针和分配失败
伪代码强调思想
真代码必须承担运行风险

10.2 顺序表插入：伪代码 vs 真代码¶

原书伪代码（整理版）：

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= MaxSize) return false;

    for (int j = L.length; j >= i; --j) {
        L.data[j] = L.data[j - 1]; // 后移元素
    }

    L.data[i - 1] = e;
    L.length++;
    return true;
}

真实代码（可运行 C 版）：

/* 在第 pos 个位置插入元素 value，pos 从 1 开始计数。 */
bool SeqListInsert(SeqList *list, int pos, ElemType value) {
    int i;

    if (list == NULL || pos < 1 || pos > list->length + 1) {
        return false;  /* 插入位置非法 */
    }

    if (!EnsureSeqListCapacity(list)) {
        return false;  /* 容量不够且扩容失败 */
    }

    /* 从后往前搬移，避免覆盖原有元素。 */
    for (i = list->length; i >= pos; --i) {
        list->data[i] = list->data[i - 1];
    }

    list->data[pos - 1] = value; /* 在空出来的位置放新元素 */
    list->length++;
    return true;
}

关键差别：

原书版本默认静态表容量固定
真代码里补了扩容逻辑
真代码通过注释明确说明“为什么要从后往前搬”

10.3 顺序表删除：伪代码 vs 真代码¶

原书伪代码（整理版）：

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;

    e = L.data[i - 1];
    for (int j = i; j < L.length; ++j) {
        L.data[j - 1] = L.data[j]; // 前移补位
    }

    L.length--;
    return true;
}

真实代码（可运行 C 版）：

/* 删除第 pos 个元素，并用 deleted_value 带回被删元素。 */
bool SeqListDelete(SeqList *list, int pos, ElemType *deleted_value) {
    int i;

    if (list == NULL || pos < 1 || pos > list->length) {
        return false;  /* 删除位置非法 */
    }

    if (deleted_value != NULL) {
        *deleted_value = list->data[pos - 1]; /* 保留被删值 */
    }

    /* 删除后让后面的元素整体前移，补上空洞。 */
    for (i = pos; i < list->length; ++i) {
        list->data[i - 1] = list->data[i];
    }

    list->length--;
    return true;
}

10.4 单链表初始化：伪代码 vs 真代码¶

原书伪代码（整理版）：

bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode)); // 创建头结点
    L->next = NULL;                     // 空表
    return true;
}

真实代码（可运行 C 版）：

/* 初始化带头结点单链表。 */
bool InitLinkList(LinkList *list) {
    if (list == NULL) {
        return false;  /* 参数本身不能为空 */
    }

    list->head = (LNode *)malloc(sizeof(LNode));
    if (list->head == NULL) {
        return false;  /* 申请头结点失败 */
    }

    list->head->next = NULL; /* 头结点后面暂时没有数据结点 */
    return true;
}

关键差别：

真实代码必须区分“链表对象为空”和“头结点为空”
注释会告诉你：这里是“带头结点”方案

10.5 单链表插入：伪代码 vs 真代码¶

原书伪代码（整理版）：

bool ListInsert(LinkList &L, int i, ElemType e) {
    p = L; j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL) return false;

    s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

真实代码（可运行 C 版）：

/* 在第 pos 个位置插入结点，本质是“先找前驱，再改指针”。 */
bool LinkListInsert(LinkList *list, int pos, ElemType value) {
    int index = 0;
    LNode *prev;
    LNode *node;

    if (list == NULL || list->head == NULL || pos < 1) {
        return false;  /* 参数或位置非法 */
    }

    prev = list->head;
    while (prev != NULL && index < pos - 1) {
        prev = prev->next;
        index++;
    }

    if (prev == NULL) {
        return false;  /* 没找到第 pos-1 个结点 */
    }

    node = (LNode *)malloc(sizeof(LNode));
    if (node == NULL) {
        return false;  /* 新结点申请失败 */
    }

    /* 先让新结点连向后继，再让前驱连向新结点。 */
    node->data = value;
    node->next = prev->next;
    prev->next = node;
    return true;
}

这一段最该背下来的不是代码，而是指针操作顺序：

先接后面，再改前面

10.6 单链表删除：伪代码 vs 真代码¶

原书伪代码（整理版）：

bool ListDelete(LinkList &L, int i, ElemType &e) {
    p = L; j = 0;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p == NULL || p->next == NULL) return false;

    q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

真实代码（可运行 C 版）：

/* 删除第 pos 个结点，本质是让前驱跳过目标结点。 */
bool LinkListDelete(LinkList *list, int pos, ElemType *deleted_value) {
    int index = 0;
    LNode *prev;
    LNode *target;

    if (list == NULL || list->head == NULL || pos < 1) {
        return false;
    }

    prev = list->head;
    while (prev != NULL && index < pos - 1) {
        prev = prev->next;
        index++;
    }

    if (prev == NULL || prev->next == NULL) {
        return false;  /* 目标位置不存在 */
    }

    target = prev->next;
    if (deleted_value != NULL) {
        *deleted_value = target->data; /* 返回被删元素 */
    }

    /* 先断链，再释放目标结点。 */
    prev->next = target->next;
    free(target);
    return true;
}

10.7 单链表逆置：思路版 vs 真代码¶

教材里很多时候只会告诉你“头插法逆置”这个思想，但真正写成代码时，学生往往会卡住。

真实代码（带注释）：

/* 单链表逆置：不断摘下当前结点，头插到新表前面。 */
void ReverseLinkList(LinkList *list) {
    LNode *curr;
    LNode *next;
    LNode *new_head;

    if (list == NULL || list->head == NULL) {
        return;
    }

    curr = list->head->next;
    new_head = NULL;
    while (curr != NULL) {
        next = curr->next;      /* 先记住后继，避免断链后找不到 */
        curr->next = new_head;  /* 当前结点头插到新链表前面 */
        new_head = curr;        /* 更新新链表表头 */
        curr = next;            /* 继续处理原链表的下一个结点 */
    }
    list->head->next = new_head;
}

10.8 双链表后插：伪代码 vs 真代码¶

原书思想版：

s->next = p->next;
if (p->next != NULL) p->next->prior = s;
s->prior = p;
p->next = s;

真实代码（可运行 C 版）：

/* 在给定结点后插入一个新结点。 */
bool DLinkListInsertAfter(DNode *node, ElemType value) {
    DNode *new_node;

    if (node == NULL) {
        return false;
    }

    new_node = (DNode *)malloc(sizeof(DNode));
    if (new_node == NULL) {
        return false;
    }

    new_node->data = value;
    new_node->prev = node;
    new_node->next = node->next;

    /* 双链表要同时维护 next 和 prev 两条方向。 */
    if (node->next != NULL) {
        node->next->prev = new_node;
    }
    node->next = new_node;
    return true;
}

10.9 思维拓展题：真实代码版¶

原书思路：

先排序
再用双指针从两端夹逼

真实代码：

/* 思维拓展：输出所有和为 target 的数对。 */
void PrintPairsWithSum(ElemType *arr, int n, ElemType target) {
    int i;
    int j;

    if (arr == NULL || n <= 1) {
        return;
    }

    qsort(arr, n, sizeof(ElemType), CompareElemType); /* 先排序 */
    i = 0;
    j = n - 1;
    while (i < j) {
        ElemType sum = arr[i] + arr[j];
        if (sum == target) {
            printf("pair: %d + %d = %d/n", arr[i], arr[j], target);
            i++;
            j--;
        } else if (sum < target) {
            i++;  /* 和太小，左指针右移 */
        } else {
            j--;  /* 和太大，右指针左移 */
        }
    }
}

11. 链式表示后半段补充¶

这一节把当前版本还没显式展开的几个小节补齐成自学友好版。

11.1 双链表¶

双链表是在单链表的基础上多加了一个前驱指针。

也就是说，每个结点不只知道“下一个是谁”，还知道“前一个是谁”。

优点：

查前驱更方便
删除某结点时，如果已经拿到了该结点指针，处理更直接

缺点：

每个结点要多存一个指针
空间开销更大

最适合形成的直觉：

单链表像单向路
双链表像双向路

11.2 循环链表¶

循环链表的关键不是“长得更复杂”，而是：

最后一个结点不再指向 NULL
而是重新指回头部

优点：

从任意位置都能继续转下去
很适合轮转、循环访问类问题

代码层面最容易犯的错：

输出或遍历时忘记停止条件
一不小心就死循环

所以循环链表的代码里，判断条件永远比普通链表更重要。

11.3 静态链表¶

静态链表听起来像“链表”，但本质上：

底层仍然是数组
只不过数组元素里额外存了一个“游标 next”

也就是：

用数组模拟指针

它的意义主要有两个：

帮你理解链表的本质是“链接关系”，不一定非得靠真指针
在某些没有指针或不方便用指针的环境中，可以作为替代方案

11.4 顺序表和链表的比较¶

这一节最重要的，不是死记表格，而是学会根据场景选结构。

可以用一句非常实用的话来记：

查得多，用顺序表
改得多，用链表

再精细一点：

频繁随机访问：顺序表更合适
频繁中间插删：链表更合适
空间必须紧凑：顺序表更占优
空间连续性难保证：链表更灵活

12. 注释阅读提醒¶

你要求“.md 和 .c 都要有注释”，我这边后续会一直按这个标准做：

.md 里：
每段代码都尽量给“代码前解释 + 代码内注释 + 代码后总结”
.c 里：
每个结构体说明用途
每个函数说明作用
关键指针操作写清顺序和原因

也就是说，后面的目标不是“给你很多代码”，而是：

给你能学会的代码

13. 综合算法题对照补充¶

这一节继续把第 2 章后半段常见综合题补成“伪代码 + 真代码 + 注释”的形式。

这些题有一个共同特点：

单看教材答案，好像能懂
但一到自己写代码，就会卡在指针细节

所以这一节的重点不是“背答案”，而是把思路和代码动作真正对上。

13.1 双链表是否对称¶

题目本质：

判断一个双链表从左往右看、从右往左看是否一致

原书思路版伪代码：

// p 从前往后，q 从后往前
while (p != q && p->next != q) {
    if (p->data != q->data) return false;
    p = p->next;
    q = q->prev;
}
return true;

真实代码（带注释）：

/* 判断带头结点双链表是否关于中点对称。 */
bool IsDLinkListSymmetric(const DLinkList *list) {
    DNode *left;
    DNode *right;

    if (list == NULL || list->head == NULL) {
        return true;
    }

    left = list->head->next;
    if (left == NULL) {
        return true;  /* 空表视为对称 */
    }

    right = left;
    while (right->next != NULL) {
        right = right->next; /* 先走到尾结点 */
    }

    /* 双指针从两端同时向中间推进。 */
    while (left != right && left->prev != right) {
        if (left->data != right->data) {
            return false;
        }
        left = left->next;
        right = right->prev;
    }
    return left->data == right->data;
}

你要学会的不是这题答案，而是这种“从两端夹逼”的思维。

13.2 找两个链表的第一个公共结点¶

题目本质：

两条链表可能有公共后缀
找公共后缀的起点

原书思想版伪代码：

lenA = length(A);
lenB = length(B);

让长链表先走 |lenA-lenB| 步；
然后两个指针同步向后移动；
第一次指向同一结点的位置，就是公共结点。

真实代码（带注释）：

/* 找两个带头结点单链表的第一个公共结点。 */
LNode *FindFirstCommonNode(const LinkList *a, const LinkList *b) {
    int len_a = 0;
    int len_b = 0;
    LNode *pa;
    LNode *pb;

    if (a == NULL || b == NULL || a->head == NULL || b->head == NULL) {
        return NULL;
    }

    pa = a->head->next;
    pb = b->head->next;
    while (pa != NULL) {
        len_a++;
        pa = pa->next;
    }
    while (pb != NULL) {
        len_b++;
        pb = pb->next;
    }

    pa = a->head->next;
    pb = b->head->next;
    while (len_a > len_b) {
        pa = pa->next; /* 长链表先走，和短链表尾部对齐 */
        len_a--;
    }
    while (len_b > len_a) {
        pb = pb->next;
        len_b--;
    }

    while (pa != NULL && pb != NULL) {
        if (pa == pb) {
            return pa; /* 第一次相遇就是第一个公共结点 */
        }
        pa = pa->next;
        pb = pb->next;
    }
    return NULL;
}

核心直觉：

不是比较“值相不相等”
而是比较“是不是同一个结点地址”

13.3 删除绝对值重复的结点¶

题目本质：

一个链表中，若某个绝对值已经出现过，后面再出现绝对值相同的结点就删掉

原书思想版伪代码：

开一个辅助数组 seen[];
从头到尾扫描链表：
    若 abs(x) 没出现过，则标记并保留；
    若 abs(x) 已出现过，则删除当前结点。

真实代码（带注释）：

/* 删除单链表中绝对值重复的结点，max_abs 用来确定辅助数组大小。 */
bool RemoveAbsDuplicates(LinkList *list, int max_abs) {
    int *seen;
    LNode *prev;
    LNode *curr;

    if (list == NULL || list->head == NULL || max_abs < 0) {
        return false;
    }

    seen = (int *)calloc((size_t)max_abs + 1, sizeof(int));
    if (seen == NULL) {
        return false;
    }

    prev = list->head;
    curr = list->head->next;
    while (curr != NULL) {
        int key = abs(curr->data);

        if (seen[key]) {
            /* 绝对值重复：前驱直接跳过当前结点。 */
            prev->next = curr->next;
            free(curr);
            curr = prev->next;
        } else {
            seen[key] = 1; /* 第一次出现，做标记 */
            prev = curr;
            curr = curr->next;
        }
    }

    free(seen);
    return true;
}

这题本质上是：

用空间换时间

也就是典型的：

辅助数组/哈希思想 + 链表删除

13.4 链表重排：L1, Ln, L2, Ln-1, ...¶

这类题特别适合练链表综合能力。

题目目标：

原链表：1 -> 2 -> 3 -> 4 -> 5 -> 6
重排后：1 -> 6 -> 2 -> 5 -> 3 -> 4

原书思想一般会分三步：

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

真实代码（带注释）：

/* 把链表重排为 L1, Ln, L2, Ln-1 ... 的形式。 */
void ReorderListFrontBack(LinkList *list) {
    LNode *slow;
    LNode *fast;
    LNode *first;
    LNode *second;
    LNode *next_first;
    LNode *next_second;

    if (list == NULL || list->head == NULL || list->head->next == NULL ||
        list->head->next->next == NULL) {
        return;
    }

    slow = list->head->next;
    fast = list->head->next;

    /* 快慢指针找中点。 */
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    second = slow->next;
    slow->next = NULL; /* 断开前后两段 */
    second = ReverseNodeChain(second); /* 逆置后半段 */

    first = list->head->next;
    while (second != NULL) {
        next_first = first->next;
        next_second = second->next;

        first->next = second;      /* 插入一个后半段结点 */
        second->next = next_first; /* 再接回前半段 */

        first = next_first;
        second = next_second;
        if (first == NULL) {
            break;
        }
    }
}

这题很适合你练下面三件事：

快慢指针
链表逆置
多段链表合并

13.5 判断链表是否有环，并找出环的入口¶

这题是链表里非常经典的一类题，很多同学一开始会本能地想：

“能不能开一个集合，把访问过的结点地址都记下来？”

这样当然能做，但书里更看重的是不用额外集合的做法，也就是著名的：

Floyd 判圈法
也叫“快慢指针判环”

原书思想版伪代码：

slow = head;
fast = head;

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

    if (slow == fast) {
        说明有环；
        break;
    }
}

若 fast == NULL 或 fast->next == NULL：
    说明无环；

若有环：
    p1 从 head 出发；
    p2 从相遇点出发；
    两者每次都走一步；
    再次相遇的位置就是环入口。

真实代码（带注释）：

/* 用 Floyd 判圈法寻找单链表中的环入口；若无环则返回 NULL。 */
LNode *FindLoopStartNode(LNode *head) {
    LNode *fast = head;
    LNode *slow = head;
    LNode *p1;
    LNode *p2;

    if (head == NULL) {
        return NULL;
    }

    /* 第一阶段：判断 fast 和 slow 是否会在环中相遇。 */
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;           /* 慢指针每次走一步 */
        fast = fast->next->next;     /* 快指针每次走两步 */
        if (slow == fast) {
            break;
        }
    }

    if (fast == NULL || fast->next == NULL) {
        return NULL; /* 能走到 NULL，说明无环 */
    }

    /* 第二阶段：从头结点和相遇点同时出发，再次相遇处即为环入口。 */
    p1 = head;
    p2 = slow;
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1;
}

这题最值得你真正吃透的地方是：

“为什么再走一次就会在入口相遇？”

你可以先记住结论，再慢慢推公式；第一次学习时，先会用，再去完全证明，是很正常的顺序。

更形象一点理解：

快指针像在操场上跑得更快的人
如果操场是闭环，它迟早会从后面追上慢指针
追上之后，再让一个人从起点出发，一个人从相遇点出发，他们会在“入场口”碰头

13.6 合并两个循环单链表¶

循环链表这类题最容易把人绕晕的点在于：

它没有真正的 NULL 结尾
你不能再用“走到空为止”的思路
你必须始终知道“哪里是头结点，哪里是尾结点”

原书思想版伪代码：

找到循环链表 A 的尾结点 tailA；
找到循环链表 B 的尾结点 tailB；

tailA->next = B 的首元结点；
tailB->next = A 的头结点；

这样合并后仍然是一个循环链表。

真实代码（带注释）：

/* 连接两个带头结点循环单链表，使结果仍然是循环链表。 */
bool JoinCircularLists(CircularList *a, CircularList *b) {
    CNode *tail_a;
    CNode *tail_b;

    if (a == NULL || b == NULL || a->head == NULL || b->head == NULL) {
        return false;
    }

    tail_a = a->head;
    while (tail_a->next != a->head) {
        tail_a = tail_a->next;
    }

    tail_b = b->head;
    while (tail_b->next != b->head) {
        tail_b = tail_b->next;
    }

    /* 把 A 的尾接到 B 的首元结点，把 B 的尾接回 A 的头结点。 */
    if (b->head->next != b->head) {
        tail_a->next = b->head->next;
        tail_b->next = a->head;
    }

    /* B 的头结点已不再需要，避免后续误用。 */
    free(b->head);
    b->head = NULL;
    return true;
}

这里你一定要注意一个链表题里的老坑：

“接线顺序不能乱”

如果你先把某个指针改掉，很可能后面就找不到原来的链了。

更直观地说：

你现在是在给两条环形轨道重新接轨
只要有一处接错，整个环就可能断掉，或者变成死循环

13.7 求链表对称位置元素和的最大值¶

这题很适合作为“链表综合题”练手，因为它把几个知识点揉在一起了：

找中点
逆置后半段
双指针同步比较

题目意思可以理解成：

链表是 1 -> 100 -> 2 -> 90 -> 3 -> 80
对称位置配对就是：
1 + 80
100 + 3
2 + 90
看哪个和最大

原书思想版伪代码：

slow 和 fast 同时从首元结点出发；
用快慢指针找到中点；

把后半段链表逆置；

left 指向前半段起点；
right 指向逆置后的后半段起点；

while (right != NULL) {
    sum = left->data + right->data;
    更新最大值；
    left 和 right 同时后移；
}

真实代码（带注释）：

/* 求链表“对称位置元素和”的最大值：首尾、次首次尾…… */
int PairSumLinkList(LinkList *list) {
    LNode *fast;
    LNode *slow;
    LNode *second_half;
    LNode *left;
    LNode *right;
    int max_sum = 0;

    if (list == NULL || list->head == NULL || list->head->next == NULL) {
        return 0;
    }

    fast = list->head->next;
    slow = list->head->next;

    /* 快慢指针找中点，slow 最终停在前半段尾部附近。 */
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    second_half = ReverseNodeChain(slow);
    left = list->head->next;
    right = second_half;

    while (right != NULL) {
        int sum = left->data + right->data;
        if (sum > max_sum) {
            max_sum = sum;
        }
        left = left->next;
        right = right->next;
    }

    return max_sum;
}

这题的核心直觉其实很漂亮：

数组里“首尾配对”很容易，因为能随机访问
链表里做这件事很难，因为你不能直接一下跳到尾巴
所以我们先把后半段翻过来，硬生生把“尾到头”的访问，改造成“从前往后”的访问

这就是链表题特别常见的一类思路：

先改结构
再做计算

13.8 删除顺序表中位于给定区间的元素¶

顺序表综合题里，这类题出场率非常高，因为它特别能考你对“覆盖式删除”的理解。

题目模型通常像这样：

删除顺序表中所有值落在 [s, t] 区间内的元素
要求剩余元素仍然连续存放
尽量不要一个元素删一次就移动一次

原书思想版伪代码：

write = 0;
for read 从 0 到 length-1:
    if data[read] 不在 [s, t] 中:
        data[write] = data[read];
        write++;
length = write;

真实代码（带注释）：

/* 删除顺序表中值位于 [s, t] 区间内的元素。 */
bool RemoveRangeSeqList(SeqList *list, ElemType s, ElemType t) {
    int read_index;
    int write_index;

    if (list == NULL || list->data == NULL || s > t) {
        return false;
    }

    write_index = 0;
    for (read_index = 0; read_index < list->length; read_index++) {
        ElemType value = list->data[read_index];
        if (value < s || value > t) {
            list->data[write_index++] = value; /* 保留区间外元素，向前压缩 */
        }
    }
    list->length = write_index;
    return true;
}

这题最重要的直觉是：

不是“删一个移一次”
而是“把该保留的元素统一往前写”

这类思路在数组、字符串、顺序表里都特别常见。

13.9 删除递增有序顺序表中的重复元素¶

这道题是顺序表版的经典“双指针”。

如果原表是：

1 2 2 3 5 5 8

去重后应该变成：

1 2 3 5 8

原书思想版伪代码：

slow 指向当前保留下来的最后一个不同元素；
fast 从前往后扫描；

若 data[fast] != data[slow]：
    slow++;
    data[slow] = data[fast];

最后 length = slow + 1;

真实代码（带注释）：

/* 删除递增有序顺序表中的重复元素，保留每个值第一次出现的位置。 */
bool DeduplicateSortedSeqList(SeqList *list) {
    int slow;
    int fast;

    if (list == NULL || list->data == NULL) {
        return false;
    }
    if (list->length <= 1) {
        return true;
    }

    slow = 0;
    for (fast = 1; fast < list->length; fast++) {
        if (list->data[fast] != list->data[slow]) {
            list->data[++slow] = list->data[fast];
        }
    }
    list->length = slow + 1;
    return true;
}

这题背后的方法特别值得记住：

slow 负责维护“有效区间”
fast 负责扫描“原始区间”

你可以把它想成：

前面是一块“已经整理好的区域”
后面是“等待检查的区域”

13.10 合并两个递增有序顺序表¶

这题本质上是在考：

两个有序源
一个有序结果
指针/下标如何同步推进

原书思想版伪代码：

i = j = k = 0;

while (A 和 B 都没扫完) {
    比较 A[i] 和 B[j];
    较小者写入 C[k]；
    对应下标前进；
    k++;
}

把剩余未处理部分整体复制到 C。

真实代码（带注释）：

/* 合并两个递增有序顺序表，结果写入 result。 */
bool MergeSortedSeqLists(const SeqList *a, const SeqList *b, SeqList *result) {
    int i = 0;
    int j = 0;
    int k = 0;

    if (a == NULL || b == NULL || result == NULL) {
        return false;
    }
    if (!InitSeqList(result, a->length + b->length)) {
        return false;
    }

    while (i < a->length && j < b->length) {
        if (a->data[i] <= b->data[j]) {
            result->data[k++] = a->data[i++];
        } else {
            result->data[k++] = b->data[j++];
        }
    }
    while (i < a->length) {
        result->data[k++] = a->data[i++];
    }
    while (j < b->length) {
        result->data[k++] = b->data[j++];
    }
    result->length = k;
    return true;
}

这题的感觉其实很像：

两条已经排好队的队伍
每次把更靠前的人先放进新队伍

学会它以后，后面学归并排序会轻松很多。

13.11 合并两个递增有序单链表¶

如果把上一题从顺序表搬到链表上，难点会马上变成：

不能随机访问
不能直接用下标
只能靠指针一个一个接

原书思想版伪代码：

pa 指向链表 A 首元结点；
pb 指向链表 B 首元结点；
tail 指向结果链表尾部；

while (pa != NULL 且 pb != NULL) {
    把较小结点接到 tail 后面；
    对应指针后移；
    tail 后移；
}

把剩余部分整体接到 tail 后面。

真实代码（带注释）：

/* 合并两个递增有序单链表，复用原结点并生成新的结果链表。 */
bool MergeSortedLinkLists(LinkList *a, LinkList *b, LinkList *result) {
    LNode *pa;
    LNode *pb;
    LNode *tail;

    if (a == NULL || b == NULL || result == NULL || a->head == NULL || b->head == NULL) {
        return false;
    }
    if (!InitLinkList(result)) {
        return false;
    }

    pa = a->head->next;
    pb = b->head->next;
    tail = result->head;

    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) {
            tail->next = pa;
            pa = pa->next;
        } else {
            tail->next = pb;
            pb = pb->next;
        }
        tail = tail->next;
    }

    tail->next = (pa != NULL) ? pa : pb; /* 剩余部分整体挂到结果尾部 */
    a->head->next = NULL;
    b->head->next = NULL;
    return true;
}

这题非常锻炼你对“尾指针”的掌控。

你可以把 tail 想成：

新链表施工现场里，永远站在最末尾的工人
每接上一个新结点，他就往后挪一步

13.12 按给定值划分链表¶

这类题在考研题和面试题里都很常见。

题目通常长这样：

把链表中所有 < x 的结点放前面
所有 >= x 的结点放后面
尽量保持原有相对顺序

原书思想版伪代码：

建立 two lists:
    less 链表保存 < x 的结点
    greater 链表保存 >= x 的结点

扫描原链表：
    当前结点按值接到对应子链表尾部

最后把 less 和 greater 连起来。

真实代码（带注释）：

/* 按照 x 把单链表稳定划分为“小于 x”和“大于等于 x”两段。 */
bool PartitionLinkListByValue(LinkList *list, ElemType x) {
    LNode less_dummy;
    LNode greater_dummy;
    LNode *less_tail = &less_dummy;
    LNode *greater_tail = &greater_dummy;
    LNode *curr;

    if (list == NULL || list->head == NULL) {
        return false;
    }

    less_dummy.next = NULL;
    greater_dummy.next = NULL;
    curr = list->head->next;

    while (curr != NULL) {
        LNode *next = curr->next;
        curr->next = NULL; /* 先摘下来，再决定放到哪一段 */
        if (curr->data < x) {
            less_tail->next = curr;
            less_tail = curr;
        } else {
            greater_tail->next = curr;
            greater_tail = curr;
        }
        curr = next;
    }

    less_tail->next = greater_dummy.next;
    list->head->next = less_dummy.next;
    return true;
}

这题特别适合培养一个重要习惯：

每次改指针前，先把 next 暂存下来

否则你一旦把当前结点摘下来，后面的链就可能找不回来了。

13.13 删除顺序表中的最小元素，并用最后一个元素填补¶

这是顺序表非常经典的一道题，因为它专门考你能不能区分两种不同的删除目标：

有些题要求“保持原来相对次序”
有些题只要求“删掉元素，表仍然合法”

这题属于第二种，所以可以用一个特别省事的方法：

找到最小值
用最后一个元素补到它的位置
表长减一

原书思想版伪代码：

min_index = 0;
扫描整个顺序表，找到最小元素位置；

value = data[min_index];
data[min_index] = data[length - 1];
length--;

真实代码（带注释）：

/* 删除顺序表中的最小值，并用最后一个元素填补空位。 */
bool DeleteMinSeqList(SeqList *list, ElemType *value_out) {
    int min_index;
    int i;

    if (list == NULL || list->data == NULL || list->length == 0 || value_out == NULL) {
        return false;
    }

    min_index = 0;
    for (i = 1; i < list->length; i++) {
        if (list->data[i] < list->data[min_index]) {
            min_index = i;
        }
    }

    *value_out = list->data[min_index];
    list->data[min_index] = list->data[list->length - 1]; /* 最后一个元素补到空位 */
    list->length--;
    return true;
}

这题最容易丢分的地方是：

很多同学会下意识把后面的元素全体前移

但这里根本不需要，因为题目并没有要求保序。

13.14 原地逆置顺序表¶

顺序表逆置看起来简单，但它是后面很多“数组区间交换”“旋转数组”题的基础动作。

原书思想版伪代码：

left = 0;
right = length - 1;

while (left < right) {
    交换 data[left] 和 data[right];
    left++;
    right--;
}

真实代码（带注释）：

/* 原地逆置顺序表，首尾交换直到中间。 */
void ReverseSeqList(SeqList *list) {
    int left;
    int right;

    if (list == NULL || list->data == NULL || list->length <= 1) {
        return;
    }

    left = 0;
    right = list->length - 1;
    while (left < right) {
        ElemType temp = list->data[left];
        list->data[left] = list->data[right];
        list->data[right] = temp;
        left++;
        right--;
    }
}

你可以把它理解成：

两个人分别站在数组两头
每次交换一对，然后同时往中间走

这是典型的“双指针夹逼”。

13.15 删除递增有序单链表中的重复结点¶

顺序表去重我们前面已经做过了，链表版本会更能体现：

“重复的不是位置”
“而是结点之间的连接关系”

原书思想版伪代码：

curr 指向首元结点；

while (curr 和 curr->next 都存在) {
    if curr->data == curr->next->data:
        删除 curr->next
    else:
        curr 后移
}

真实代码（带注释）：

/* 删除递增有序单链表中的重复结点，只保留每个值第一次出现的位置。 */
bool DeduplicateSortedLinkList(LinkList *list) {
    LNode *curr;

    if (list == NULL || list->head == NULL) {
        return false;
    }

    curr = list->head->next;
    while (curr != NULL && curr->next != NULL) {
        if (curr->data == curr->next->data) {
            LNode *duplicate = curr->next;
            curr->next = duplicate->next; /* 跳过重复结点 */
            free(duplicate);
        } else {
            curr = curr->next;
        }
    }
    return true;
}

这题真正的训练点是：

删除当前后继结点时，curr 先别动

因为删完以后，新的 curr->next 仍然可能和 curr 相同。

13.16 找单链表的中间结点¶

这是快慢指针最核心、最常见、最该熟练掌握的用途之一。

原书思想版伪代码：

slow = first;
fast = first;

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

slow 所在位置就是中间结点。

真实代码（带注释）：

/* 用快慢指针找到单链表的中间结点。 */
LNode *FindMiddleNode(const LinkList *list) {
    LNode *slow;
    LNode *fast;

    if (list == NULL || list->head == NULL || list->head->next == NULL) {
        return NULL;
    }

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

形象一点理解：

slow 像正常走路的人
fast 像小跑的人
当小跑的人冲到终点时，走路的人正好差不多走到中间

这类题你越熟，后面找中点、判回文、链表重排都会越顺。

13.17 求两个递增有序链表的公共元素¶

这是“有序结构 + 双指针”的另一类高频题。

比如：

A：1 2 3 5 7 9
B：2 3 4 5 8 9

那么公共元素就是：

2 3 5 9

原书思想版伪代码：

pa 指向 A 首元结点；
pb 指向 B 首元结点；

while (pa != NULL 且 pb != NULL) {
    若 pa < pb，则 pa 后移；
    若 pa > pb，则 pb 后移；
    若相等，则输出/保存该值，并让两者都后移；
}

真实代码（带注释）：

/* 求两个递增有序单链表的公共元素，结果写入新链表。 */
bool IntersectSortedLinkLists(const LinkList *a, const LinkList *b, LinkList *result) {
    LNode *pa;
    LNode *pb;
    LNode *tail;

    if (a == NULL || b == NULL || result == NULL || a->head == NULL || b->head == NULL) {
        return false;
    }
    if (!InitLinkList(result)) {
        return false;
    }

    pa = a->head->next;
    pb = b->head->next;
    tail = result->head;

    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pb = pb->next;
        } else {
            LNode *node = (LNode *)malloc(sizeof(LNode));
            if (node == NULL) {
                DestroyLinkList(result);
                return false;
            }
            node->data = pa->data;
            node->next = NULL;
            tail->next = node;
            tail = node;
            pa = pa->next;
            pb = pb->next;
        }
    }
    return true;
}

这题很像两个人拿着两份有序名单在对照：

谁小，谁先往后看
一旦相同，就记下来

这其实就是“有序性帮你省掉大量无效比较”的典型例子。

14. 本轮新增代码对照重点¶

为了让这一章更接近“增强版教材”，我这轮又补了两批高频综合题：

有环链表找入口
循环链表合并
链表对称位置求最大和
顺序表区间删除
有序顺序表去重
有序顺序表合并
有序链表合并
按值划分链表
删除最小值并尾元素补位
顺序表原地逆置
有序链表去重
找链表中间结点
有序链表公共元素

你会发现它们不是零散题，而是把第 2 章很多知识点串起来了：

指针追赶
链表逆置
头结点与尾结点处理
链式结构重连
综合题建模

15. 代码阅读建议¶

建议按下面的顺序阅读本章代码：

先看 本书第2章正文 里的伪代码和解释
再看 第2章普通代码版 里的带注释实现
最后对着代码自己手推一遍指针变化

尤其是链表题，真正能学会的关键不是“看懂”，而是：

知道每一次 next 改动前后，链有没有断

17. 题型分类索引¶

为了让这一章真正能当“自学教材”使用，下面我把已经补进去的高频题按题型重新整理一遍。

你后面复习时，不一定要从头读到尾；完全可以按自己薄弱的题型直接跳着查。

17.1 顺序表基础操作类¶

这类题的核心是：

连续存储
覆盖式删除
元素搬移
下标控制

对应题目：

顺序表插入
顺序表删除
删除区间元素
删除最小元素并用尾元素补位
原地逆置顺序表
递增有序顺序表去重
两个递增有序顺序表合并

如果你这类题常错，优先检查：

下标是从 0 还是逻辑位序从 1
删除后是否正确更新 length
是否错误地多搬或少搬了一个元素

17.2 单链表基础操作类¶

这类题的核心是：

指针修改顺序
前驱结点定位
头结点是否存在

对应题目：

单链表插入
单链表删除
头插法建表
尾插法建表
单链表逆置
找倒数第 k 个结点
找中间结点

这类题最常见的失误是：

指针改太早，导致后续链断掉
漏判空指针
把头结点和首元结点混了

17.3 有序表/有序链表类¶

这类题几乎都在考：

“有序性”能不能被你利用起来

对应题目：

递增有序顺序表去重
两个递增有序顺序表合并
两个递增有序链表合并
递增有序链表去重
两个递增有序链表求交集

这类题的共通思路往往是：

双指针
谁小谁先动
相等时一起动

17.4 链表结构改造类¶

这类题是第 2 章最有“算法味”的部分。

对应题目：

链表重排 L1, Ln, L2, Ln-1...
按值划分链表
删除绝对值重复结点
对称位置元素和最大值

这类题常常不是直接算，而是：

先改链表结构
再做目标操作

这也是为什么第 2 章里“逆置链表”这么重要，因为它经常是后续综合题里的中间步骤。

17.5 指针追赶与特殊结构类¶

这类题的特点是：

不是普通遍历能优雅解决的
需要你对“链上相遇”和“链上对齐”有感觉

对应题目：

找两个链表的第一个公共结点
Floyd 判圈并找环入口
双链表是否对称
合并两个循环链表

这类题最需要记住的不是代码，而是“为什么这个方法有效”：

为什么长度对齐后能找到公共结点
为什么快慢指针相遇后再走会到环入口
为什么双链表可以从两端夹逼

18. 刷题导航¶

建议按下面的路线完成本章刷题训练。

18.1 基础训练：先把基本动作练熟¶

目标：

能独立写出最基础的顺序表和单链表操作

建议顺序：

顺序表插入
顺序表删除
单链表插入
单链表删除
头插法、尾插法
单链表逆置

这一部分不要追求做难题，先把“删、插、查、改指针”练稳。

18.2 进阶训练：把有序结构题刷通¶

目标：

看见“递增有序”四个字就能马上想到双指针/归并思路

建议顺序：

有序顺序表去重
有序顺序表合并
有序链表合并
有序链表去重
有序链表求交集

这里训练的其实不是某一题，而是：

“利用有序性减少比较”

18.3 强化训练：刷链表综合题¶

目标：

学会把多个基本动作拼起来

建议顺序：

找中间结点
找倒数第 k 个结点
删除绝对值重复结点
按值划分链表
链表重排
对称位置元素和最大值

这里的关键不是背答案，而是训练自己拆解：

这题能不能分成两到三步
哪一步是“找位置”
哪一步是“改结构”
哪一步是“输出结果”

18.4 第四轮：攻克最容易卡人的题¶

目标：

真正吃透“链式结构里的追赶、相遇、对齐”

建议顺序：

两链表第一个公共结点
有环链表找入口
双链表对称判断
循环链表合并

如果你能在这一部分讲清楚“为什么这样做对”，那第 2 章就是真的学进去了。

19. 本章自学检查清单¶

学完第 2 章后，如果你想判断自己到底有没有学扎实，可以直接拿这份清单自检。

19.1 概念层¶

你能说清楚顺序表和链表的本质区别吗？
你能解释为什么顺序表支持随机访问，而链表不支持吗？
你能说清头结点、头指针、首元结点的区别吗？

19.2 代码层¶

你能不看答案写出顺序表插入和删除吗？
你能不看答案写出单链表插入和删除吗？
你能独立写出单链表逆置吗？
你能自己写出一个快慢指针找中点吗？

19.3 综合题层¶

你看到“有序”会不会主动想到双指针？
你看到“公共结点”会不会想到先对齐长度？
你看到“有环”会不会想到 Floyd 判圈？
你看到“前后交替重排”会不会想到“找中点 + 逆置 + 合并”？

19.4 真正达标的标准¶

如果下面四条你都能做到，那么第 2 章基本就算学扎实了：

能讲清思路
能写出伪代码
能写出真实 C 代码
能解释关键指针为什么这样改

20. 本章收口说明¶

到这里，第 2 章已经基本具备“独立自学增强版”的样子了。

它现在包含：

原书主线知识
关键定义和概念解释
更易理解的白话说明
原书思路版伪代码
对应真实 C 代码
代码注释
高频综合题扩展
题型索引
刷题导航
自学检查清单

换句话说，这一章现在已经不只是“看过”，而是更接近：

能学
能练
能查
能写
能编译验证

22. 逐行拆解示范¶

下面对第 2 章最核心的三个代码动作再做一次“逐行级”的文字拆解。

你会发现，真正难的往往不是算法本身，而是：

哪一行先写
哪一行后写
某一步如果换顺序会不会断链

22.1 顺序表插入：为什么一定要从后往前搬¶

真实代码核心片段：

bool SeqListInsert(SeqList *list, int index, ElemType value) {
    int i;

    if (list == NULL || list->data == NULL) {
        return false;
    }
    if (index < 1 || index > list->length + 1) {
        return false;
    }
    if (!EnsureSeqListCapacity(list, list->length + 1)) {
        return false;
    }

    for (i = list->length; i >= index; i--) {
        list->data[i] = list->data[i - 1];
    }
    list->data[index - 1] = value;
    list->length++;
    return true;
}

逐行理解：

int i;
先声明循环变量，后面要用它控制搬移过程。
if (list == NULL || list->data == NULL)
先防御性判断，避免一上来就访问空指针。
if (index < 1 || index > list->length + 1)
检查插入位置是否合法。
注意这里是“位序”概念，不是数组下标。
EnsureSeqListCapacity(...)
先保证空间够，再做真正插入。
不然你还没搬移，就可能已经写越界了。
for (i = list->length; i >= index; i--)
这里必须从后往前搬。
因为如果你从前往后搬，前面的值会把后面的原值覆盖掉。
list->data[i] = list->data[i - 1];
把后一格腾出来，给插入位置让位。
list->data[index - 1] = value;
真正把新元素放到目标位置。
list->length++;
最后再更新长度。
因为前面的搬移过程用到的还是旧长度。

这题最核心的记忆点就是一句话：

顺序表插入的本质，不是“加一个数”，而是“先挪位置，再落点”

22.2 单链表插入：为什么要先接后面，再改前面¶

真实代码核心片段：

bool LinkListInsert(LinkList *list, int index, ElemType value) {
    int j;
    LNode *prev;
    LNode *node;

    if (list == NULL || list->head == NULL || index < 1) {
        return false;
    }

    prev = list->head;
    for (j = 1; j < index && prev != NULL; j++) {
        prev = prev->next;
    }
    if (prev == NULL) {
        return false;
    }

    node = (LNode *)malloc(sizeof(LNode));
    if (node == NULL) {
        return false;
    }
    node->data = value;
    node->next = prev->next;
    prev->next = node;
    return true;
}

逐行理解：

prev = list->head;
先让 prev 从头结点出发，准备去找插入位置的前驱。
for (...) prev = prev->next;
一步一步往后走，直到走到第 index-1 个位置对应的结点。
if (prev == NULL)
如果前驱都找不到，说明插入位置非法。
node = malloc(...)
真正创建新结点。
node->data = value;
先把数据装进新结点。
node->next = prev->next;
这一步特别关键：先让新结点接住后面的链。
prev->next = node;
再让前驱指向新结点。

为什么顺序一定不能反？

因为如果你先写：

prev->next = node;

而这时 node->next 还没接好，那么：

原来 prev 后面的那段链
就有可能丢掉

所以单链表插入最重要的不是背代码，而是记住这句：

先接后面，再改前面

22.3 单链表逆置：每次都把当前结点“头插”到新链表前面¶

真实代码核心片段：

void ReverseLinkList(LinkList *list) {
    LNode *curr;
    LNode *next;
    LNode *new_head;

    if (list == NULL || list->head == NULL) {
        return;
    }

    curr = list->head->next;
    new_head = NULL;
    while (curr != NULL) {
        next = curr->next;
        curr->next = new_head;
        new_head = curr;
        curr = next;
    }
    list->head->next = new_head;
}

逐行理解：

curr = list->head->next;
curr 指向当前正在处理的结点。
new_head = NULL;
先准备一条空的新链，后面把旧链结点一个个搬过去。
while (curr != NULL)
只要旧链还没处理完，就继续循环。
next = curr->next;
先把后继存下来。
这是逆置链表最不能少的一步。
curr->next = new_head;
让当前结点头插到新链表最前面。
new_head = curr;
更新新链表表头。
curr = next;
回到旧链表里继续处理下一个结点。
list->head->next = new_head;
最后把带头结点链表重新接回逆置后的新链。

这段代码的直觉图像是：

从旧链表里一个个摘结点
每摘一个，就插到新链表最前面
摘完以后，方向自然就反过来了

所以逆置链表的本质并不是“整体翻过来”，而是：

不断做头插

23. 后续代码注释标准¶

24. 原书试题区整理版¶

24.1 这一版整理的作用¶

这一部分不是把原书题目机械抄一遍，而是把第 2 章原书试题按“考法”重新归类。

这样整理的目的主要有两个：

学生一看到题，先能判断这是哪一类线性表问题
后面做逐题详细解答时，可以直接沿着这个分类继续展开

当前这一版主要先做三件事：

把原书第 2 章试题按知识块重新归组
每类题都说明“它在考什么”
给出对应的做题思路和易错点

24.2 线性表基本概念与顺序表基础题¶

这一类题通常围绕：

线性表的定义
顺序表的特点
随机访问为什么成立
静态分配和动态分配的区别
插入、删除的时间复杂度

这类题表面像概念题，但本质上在考：

你是否理解“线性表”和“顺序存储”是两层概念
你是否知道顺序表为什么查得快、改得慢

做题思路：

先判断它在问逻辑结构还是存储结构
再判断它问的是访问代价还是修改代价
最后回到“连续存储 + 需要搬移”这条主线

易错点：

把线性表和顺序表混成一个概念
只记“随机访问快”，忘记“插删要搬移”

24.3 顺序表操作题¶

这一类题通常围绕：

顺序表插入
顺序表删除
区间删除
删除最小值
去重
原地逆置
有序顺序表合并

这类题最常考的不是定义，而是：

下标怎么动
元素为什么要从后往前搬
哪些题适合双指针、哪些题适合覆盖写回

做题思路：

先判断是“保留哪些元素”还是“删除哪些元素”
再判断是否需要保持原相对次序
最后选：
整体搬移
双指针覆盖
直接交换 / 逆置

易错点：

插入时从前往后搬导致覆盖数据
删除区间元素时边删边搬，逻辑变乱
以为所有题都只能老老实实一项一项删

24.4 单链表基础操作题¶

这一类题通常围绕：

初始化
按位查找
按值查找
插入
删除
头插法建表
尾插法建表
逆置

这类题最核心的考点是：

指针到底指向谁
修改指针时顺序为什么重要

做题思路：

先明确是否带头结点
先找前驱还是直接找目标结点
修改链接时，一定先保住后路，再改前面的指针

易错点：

把头指针和头结点混掉
插入或删除时断链
逆置时丢掉后继结点

24.5 有序链表与综合改造题¶

这一类题通常围绕：

有序链表合并
有序链表去重
公共结点
按值划分链表
找中间结点
找环入口
重排链表

这类题最常考的是：

双指针
快慢指针
前驱结点维护
链表拆分和再拼接

做题思路：

先判断题目本质是“找位置”“删结点”还是“改结构”
再决定是用：
前驱 + 当前
快慢指针
双链合并
分段重连

易错点：

只会写基础链表，不会做结构改造
快慢指针里不知道每个指针此刻代表什么
合并或重排时改指针顺序错误

24.6 双链表、循环链表、静态链表题¶

这一类题通常围绕：

双链表插入 / 删除
双链表对称判断
循环链表遍历
循环链表合并
静态链表的基本思想

这类题最该抓的是：

双链表比单链表多了前驱指针维护
循环链表比普通链表多了“终止条件更容易出错”
静态链表本质上是“数组模拟链表”

做题思路：

双链表：始终同时检查 prev 和 next
循环链表：先看循环边界，再看起点与终点怎么判
静态链表：把“下标”当成“指针”去理解

易错点：

双链表只改一边指针
循环链表遍历时写成死循环
静态链表仍然按普通数组思维去看

24.7 这一版整理后的使用方法¶

现在最推荐这样用这部分：

做题前先判断题目属于顺序表、单链表还是综合改造题
再看这一类题最常见的做题主线
做不出来时，再回看后面的逐题详细解答版和对应代码

这样会比“从头往后刷一遍”更稳，因为学生会先建立题型识别能力。

25. 原书试题逐题详细解答版（基础部分）¶

25.1 高频题 1：为什么顺序表支持随机访问¶

题目本质：

这类题不是在问“顺序表查得快”这么一句话，而是在问：

为什么你能直接通过下标跳到第 i 个元素。

正确结论：

顺序表支持随机访问，是因为元素按逻辑顺序连续存放，地址可以直接按下标计算

详细思路：

顺序表里的元素在存储空间中通常是连续的
一旦知道起始地址和单个元素大小
第 i 个元素的位置就能直接算出来
所以访问不需要一个一个往后走

易错点：

只背“随机访问快”，却说不清“为什么快”
把顺序表和链表都当成“反正都存元素”

25.2 高频题 2：为什么顺序表插入要从后往前搬¶

题目本质：

这类题在考的是“覆盖风险”。

正确结论：

顺序表插入时通常要从后往前搬移元素

详细思路：

插入位置后面的元素都要整体后移一格
如果从前往后搬，前面的元素一写过去，就可能把后面还没来得及读的元素覆盖掉
从后往前搬，就能保证后面的旧值总是先被保存到新位置
所以不会丢数据

易错点：

只知道“要搬”，但不知道为什么是从后往前
觉得前后顺序无所谓

25.3 高频题 3：为什么顺序表删除区间元素更适合“覆盖写回”¶

题目本质：

这类题在考的是你有没有从“逐个删”升级到“整体保留”的思维。

正确结论：

删除区间元素时，常用双指针或覆盖写回方式更高效、更清晰

详细思路：

如果一边删一边搬，很容易把逻辑写乱
更稳的方法是：
一个指针扫描原数组
一个指针写入保留下来的元素
最后一次性更新长度
这样思路是“保留我想要的”，而不是“反复删除我不要的”

易错点：

把删除题都写成嵌套搬移
长度更新时机混乱

25.4 高频题 4：头指针和头结点为什么容易混¶

题目本质：

这类题在考的是链表最基础但最容易长期混淆的概念。

正确结论：

头指针是指向链表第一个结点的指针变量
头结点是链表最前面额外设置的一个结点

详细思路：

有头结点时，头指针通常指向头结点
无头结点时，头指针直接指向第一个数据结点
所以“头指针”是一种指针角色，“头结点”是一个实际存在的结点
两者不是一个层级的概念

易错点：

把它们当成同一个东西
一旦题目说“带头结点”，代码里还是按无头结点写

25.5 高频题 5：单链表插入为什么要先接后面，再改前面¶

题目本质：

这类题在考的是链表插入时的安全修改顺序。

正确结论：

单链表插入时通常先让新结点接上后继，再让前驱接上新结点

详细思路：

插入本质上是把新结点塞到前驱和后继之间
如果一开始就改前驱指针，而新结点还没接到后继
那原来的后继位置就可能丢掉
所以更稳的顺序是：
s->next = p->next
p->next = s

易错点：

修改顺序写反
导致后继结点丢失

25.6 高频题 6：单链表删除为什么常常要先找前驱¶

题目本质：

这类题在考的是链表删除动作真正依赖谁。

正确结论：

删除某结点时，往往更需要它的前驱，而不是它自己

详细思路：

删除一个结点，本质上不是“把它擦掉”
而是让前驱直接跨过它，连到它的后继
所以很多删除题的关键不在于先找到目标结点，而在于先找到它前面的那个结点
只有这样才能重新接链

易错点：

只会找目标结点，不会维护前驱
删除后忘记释放结点或改链

25.7 高频题 7：为什么链表逆置最怕“后路丢了”¶

题目本质：

这类题在考的是多指针改链时的时序控制。

正确结论：

链表逆置时，最关键的是在改当前结点指向之前，先保存它原来的后继

详细思路：

逆置时每个结点都要把 next 反过来
但一旦当前结点的 next 被改掉，原来的后继就不再能直接访问
所以必须先用一个临时指针存住后继
再安全地改指向

易错点：

改完当前指针后，才想起来找下一个结点
结果后半段链表直接丢失

25.8 高频题 8：为什么有序链表合并常用“双链同步前进”¶

题目本质：

这类题在考的是你有没有利用“有序”这个条件。

正确结论：

合并两个递增有序链表时，常用两个指针同步前进的方式最自然

详细思路：

两条链都已经有序
所以每次只需要比较当前两个头部较小者
把较小者接到结果链后面
对应那条链向前走一步
最后把剩余部分整体接上

易错点：

明明是有序链表题，却仍然写成“全部取出再重排”
合并时没有维护结果链尾指针

25.9 高频题 9：找公共结点为什么要先“对齐长度”¶

题目本质：

这类题在考的是双链表相交问题里的“公平起跑”思维。

正确结论：

若两链表长度不同，先让较长链表多走几步，对齐剩余长度后再同步前进

详细思路：

如果两个链表后面某段相同，那它们从公共结点到尾部的长度一定相同
所以先让长链多走差值步
这样两条链就站在“距离尾部相同”的位置
再同步往后走，第一次相遇的位置就是公共结点

易错点：

直接两链同步起跑，结果永远错位
只会暴力枚举，不会利用结构性质

25.10 高频题 10：找环入口为什么和快慢指针有关¶

题目本质：

这类题在考的是你是否真正理解了“相遇后再重启”的数学直觉。

正确结论：

判断有环常用快慢指针
找入口时，一指针从头出发，一指针从相遇点出发，再同步前进，相遇点就是入口

详细思路：

快指针一次走两步，慢指针一次走一步
如果有环，它们一定会在环内相遇
相遇后，再让一个指针回到头部
两者同步前进
再次相遇的位置，就是环入口

易错点：

只会记住“有环会相遇”，不会解释为什么能找入口
把判断有环和找入口当成两个毫无关系的动作

25.11 基础题解学习提示¶

这一部分先覆盖的是第 2 章最核心、最常见、最能建立题感的一批题：

顺序表随机访问与搬移
顺序表删除与覆盖写回
头指针 / 头结点区分
单链表插入、删除、逆置
有序链表合并
公共结点与环入口

这意味着第 2 章现在已经不只是有“代码层”和“刷题导航”，而是开始有“原书题解层”了。

站内代码入口¶

对应代码专题：第2章线性表代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读¶

← 上一章：第1章绪论下一章：第3章栈、队列和数组 →

第2章 线性表（自学版）¶

1. 本章定位¶

1.1 本章讲什么¶

1.2 为什么这一章特别重要¶

1.3 学完本章后你应该会什么¶

2. 本章结构总览¶

2.1 先搞清楚“线性表是什么”¶

2.2 再搞清楚“线性表怎么实现”¶

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

3.1 线性表的定义¶

3.1.1 相同数据类型¶

3.1.2 有限¶

3.1.3 序列¶

3.1.4 逻辑特征¶

3.1.5 线性表的几个关键特点¶

3.2 线性表的基本操作¶

3.3 本节自查题的核心结论¶

结论 1¶

结论 2¶

结论 3¶

4. 2.2 线性表的顺序表示¶

4.1 顺序表到底是什么¶

4.1.1 顺序表的关键特性¶

4.1.2 为什么它能随机访问¶

4.2 顺序表的两种分配方式¶

4.2.1 静态分配¶

4.2.2 动态分配¶

4.3 顺序表真实代码¶

4.3.1 顺序表结构体¶

4.3.2 初始化为什么要传初始容量¶

4.3.3 插入操作的真实理解¶

4.3.4 删除操作的真实理解¶

4.3.5 顺序表复杂度总结¶

按位访问¶

按值查找¶

插入¶

删除¶

4.3.6 顺序表什么时候适合用¶

5. 2.3 线性表的链式表示¶

5.1 单链表的核心思想¶

5.1.1 单链表结点¶

5.1.2 头指针和头结点¶

头指针¶

头结点¶

5.2 单链表真实代码¶

5.2.1 链表初始化¶

5.2.2 按位查找¶

5.2.3 插入操作的本质¶

5.2.4 删除操作的本质¶

5.2.5 头插法和尾插法¶

头插法¶

尾插法¶

5.2.6 链表逆置¶

5.3 顺序表 vs 单链表¶

6. 本章前半部分必须掌握的代码思想¶

7. 本章当前代码化进度¶

已补成真实 C 代码¶

尚未完全代码化但已进入提取范围¶

8. 本章当前复习提纲¶

8.1 一句话主线¶

8.2 必背结论¶

8.3 必会代码动作¶

9. 这一稿说明¶

10. 伪代码与真实代码对照¶

10.1 顺序表初始化：伪代码 vs 真代码¶

10.2 顺序表插入：伪代码 vs 真代码¶

10.3 顺序表删除：伪代码 vs 真代码¶

10.4 单链表初始化：伪代码 vs 真代码¶

10.5 单链表插入：伪代码 vs 真代码¶

10.6 单链表删除：伪代码 vs 真代码¶

10.7 单链表逆置：思路版 vs 真代码¶

10.8 双链表后插：伪代码 vs 真代码¶

10.9 思维拓展题：真实代码版¶

11. 链式表示后半段补充¶

11.1 双链表¶

11.2 循环链表¶

11.3 静态链表¶

11.4 顺序表和链表的比较¶

12. 注释阅读提醒¶

13. 综合算法题对照补充¶

第2章线性表（自学版）¶