线性表：顺序表与链表

2.1 从逻辑结构说起：什么是线性表

先抛开内存和指针，只谈「数据之间谁挨着谁」——这层关系叫逻辑结构 logical structure。 如果一组数据元素排成一条「线」，每个元素最多只有一个「前面的」和一个「后面的」， 那么这组数据就构成了一个线性表 linear list。

这里的 n 称为表长 length；n = 0 时称为空表 empty list。 括号里的每个 ai 是一个数据元素 element（也叫结点、记录）， 它本身可能很简单（一个整数），也可能很复杂（一个学生的全部信息）—— 但对线性表来说，我们只关心「它在线上的哪个位置」。

2.1.1 四个必须背下来的逻辑特征

线性表的「线性」体现在四条性质上，考试里常以判断题的形式出现，请逐条记牢：

① 存在唯一的「第一个」元素

记作 a1，称为首元素。它没有直接前驱 direct predecessor。

② 存在唯一的「最后一个」元素

记作 an，称为尾元素（表尾元素）。它没有直接后继 direct successor。

③ 除首元素外，每个元素有且仅有一个直接前驱

ai（2 ≤ i ≤ n）的直接前驱是 ai-1，唯一。

④ 除尾元素外，每个元素有且仅有一个直接后继

ai（1 ≤ i ≤ n−1）的直接后继是 ai+1，唯一。

注意「唯一」两个字的分量。③④ 合起来排除了「一个元素有两个后继」的树形分支， ① ② 又排除了「环形兜圈」的可能（严格意义上，环形结构里每个元素都有前驱后继，但没有首尾）。 所以「线性」= 一条有头有尾、不分叉、不闭合的链。

2.1.2 位序 vs 下标：一个每天都在坑人的差异

数学上我们习惯把元素写成 a1, a2, …, an， 也就是位序 position / 序号从 1 开始；而 C/C++ 数组的下标从 0 开始。 两者之间差 1：

这一条看起来是废话，但它是本章所有越界 bug 的源头。教材与考试里的 ListInsert(L, i, e)，参数 i 是位序， 合法范围是 1 ≤ i ≤ n+1（i = n+1 表示插到表尾）； 而 ListDelete(L, i, e) 的合法范围是 1 ≤ i ≤ n。 写代码时第一件事就是把边界想清楚：

2.1.3 线性表的 ADT：先把接口想清楚，再谈实现

抽象数据类型 ADT（Abstract Data Type）指的是： 一个数学模型 + 定义在该模型上的一组操作，而不关心这些操作在机器里怎么实现。 换句话说，ADT 是「说明书」，数据结构是「实物」。 对线性表而言，我们关心的是下面这些操作，而不是它用数组还是链表：

用 C++ 表达这套 ADT，最自然的做法是一个抽象基类：纯虚函数只声明接口， 具体存储细节交给派生类 SeqList 和 SinglyList 去填。 这样做的好处是：上层算法（比如「把两个线性表合并」）只依赖 List<T>&， 换实现不用改一行调用代码——这正是「面向接口编程」在数据结构课上的第一次亮相。

/* ==========================================================================
   顺序表的抽象数据类型（ADT）—— 先想清楚「有哪些操作」，再谈怎么实现
   --------------------------------------------------------------------------
   数据结构 = 逻辑结构 + 存储结构 + 运算。
   「运算」这一层只规定**做什么**（语义），不规定**怎么做**（实现）——
   这就是抽象数据类型 ADT 的含义。

   竞赛里不需要用 class 来表达 ADT：直接开全局数组 + 写几个自由函数就行，
   又快又好调试。下面先把「顺序表的运算清单」列出来（这就是 ADT），
   具体实现见后面的 seqlist.cpp。

   约定（全课件统一）：位序从 1 开始，第 i 个元素存在 a[i-1]。
     · InitList()              建空表
     · Length()                求表长 n
     · GetElem(i, e)           按位取值：取第 i 个元素，1 <= i <= n
     · LocateElem(e)           按值查找：返回位序 1..n，找不到返回 0
     · ListInsert(i, e)        在位序 i 处插入 e，1 <= i <= n+1
     · ListDelete(i, e)        删除位序 i 的元素并用 e 带回，1 <= i <= n
     · PrintList()             遍历打印
     · DestroyList()           销毁整表

   为什么找不到时返回 0 而不是 -1？
   因为位序从 1 开始，0 是天然不会被占用的「哨兵值」，
   和 C 标准库里 strchr 返回 NULL、string::find 返回 npos 是同一种思路。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;       // 顺序表最大长度
int a[N];                   // 数据存在 a[0..n-1]，逻辑位序 = 下标 + 1
int n = 0;                  // 当前表长

void InitList() { n = 0; }
int  Length()   { return n; }

/* 下面给出各操作的「空壳」，真正实现在 seqlist.cpp；
   这里只为了让这段代码能单独编译运行，直接把实现写进来也可以。 */
void PrintList() {
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    printf("\n");
}

int main() {
    InitList();
    a[n++] = 10; a[n++] = 20; a[n++] = 30;   // 直接往表尾放三个元素
    printf("表长 = %d\n", Length());          // 3
    PrintList();                              // 10 20 30
    return 0;
}

有了接口，本章接下来的所有实现都可以看作「同一份说明书的两种（乃至五种）实现方案」。 请特别注意：接口一样，复杂度却可能天差地别——这正是本讲要反复对比的主线。

2.2 顺序表：用一整块连续内存装下整张表

顺序表 sequential list 的思路极其朴素：既然元素是排成一队的， 那就把它们挨着放——在内存里申请一整块连续空间，第 1 个元素放在最前面， 第 2 个紧跟其后，依次排开。C++ 里的原生数组、std::vector、 Java 的 ArrayList、Python 的 list，底层都是这个思路。

2.2.1 内存布局与地址公式：为什么下标访问这么快

连续存放带来一个巨大的好处：只要知道第 1 个元素在哪，就能用算术算出第 i 个元素在哪， 完全不需要从头一个个找。设每个元素占 L 个字节 （L = sizeof(T)，例如 int 通常是 4 字节）， 首元素 a1 的起始地址为 LOC(a1)，那么：

这个公式的推导只有一句话：

这种「给一个下标就能直接算出地址并访问」的能力叫做随机存取 random access。 与之相对，链表只能从表头开始一格一格往后挪，叫做顺序存取 sequential access。 这两个词是本章最核心的对照，务必分清：顺序表能随机存取，链表只能顺序存取； 而「顺序存储」说的是物理布局，「顺序存取」说的是访问方式，一字之差、含义完全不同。

2.2.2 动态数组实现 SeqList<T>：size 与 capacity

顺序表有两种分配方式。静态分配直接写 T data[MaxSize];， 容量在编译期定死，一旦存满就没救（除非搬家），而且开小了浪费、开大了可能栈溢出。 动态分配在堆上 new T[cap]，容量不够时再申请一块更大的、把数据搬过去、 把旧的释放掉——这就是 std::vector 的做法，也是我们要实现的版本。

这里必须分清两个容易混淆的量：

/* ==========================================================================
   顺序表 —— 算法竞赛写法：全局数组 + 自由函数
   --------------------------------------------------------------------------
   顺序表 = 用一段连续内存依次存放元素，逻辑上相邻的两个元素物理上也相邻。
   它的两个基本事实（考点）：
     · 按下标访问是 O(1)：第 i 个元素就在 a[i-1]，一步算出来，不用找
     · 插入/删除是 O(n)：为了保持「连续」，平均要搬动一半元素

   为方便讲解和手写，下面用静态数组（比赛里最常见）。
   如果数据量超过数组上限，就把 N 开大或换成 vector<int> a; 用 push_back。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;      // 顺序表的最大长度（按要求开够，比赛时按题目数据范围定）
int a[N];                  // 元素存 a[0..n-1]：逻辑位序 i 对应下标 i-1
int n = 0;                 // 表长

void InitList() { n = 0; }
int  Length()   { return n; }
bool Empty()    { return n == 0; }

/* ---------- 按位取「值」：O(1)（顺序表的看家本领） ---------- */
bool GetElem(int i, int &e) {
    if (i < 1 || i > n) return false;   // 位序合法范围是 1..n，不是 0..n-1
    e = a[i - 1];                       // 位序 → 下标：减 1，一步到位
    return true;
}

/* ---------- 按值查找：O(n)，只能从头挨个比 ---------- */
int LocateElem(int e) {
    for (int k = 0; k < n; ++k)
        if (a[k] == e) return k + 1;    // 返回「位序」，所以是 k+1
    return 0;                           // 0 是哨兵：位序从 1 起，0 不会被占用
}

/* ---------- 插入：在位序 i 处插入 e，1 <= i <= n+1 → O(n) ----------
   从后往前依次后移一位，腾出 a[i-1] 这个位置，再放新元素。
   关键点：必须「从后往前」倒着搬，正着搬会把后面的元素覆盖掉。 */
bool ListInsert(int i, int e) {
    if (i < 1 || i > n + 1) return false;   // i = n+1 表示插到表尾，是合法的
    if (n == N) return false;               // 表满
    for (int k = n - 1; k >= i - 1; --k) a[k + 1] = a[k];
    a[i - 1] = e;
    ++n;
    return true;
}

/* ---------- 删除位序 i 的元素，用 e 带回，1 <= i <= n → O(n) ----------
   从前往后依次前移一位，把空洞填掉。 */
bool ListDelete(int i, int &e) {
    if (i < 1 || i > n) return false;
    e = a[i - 1];
    for (int k = i - 1; k < n - 1; ++k) a[k] = a[k + 1];
    --n;
    return true;
}

void PrintList() {
    for (int k = 0; k < n; ++k) printf("%d ", a[k]);
    printf("（表长 %d）\n", n);
}

int main() {
    InitList();
    for (int x : {12, 5, 33, 7, 20}) ListInsert(n + 1, x);   // 依次插到表尾建表
    PrintList();                                     // 12 5 33 7 20（表长 5）

    ListInsert(1, 99);                               // 插到最前面：后面 5 个元素全要后移
    PrintList();                                     // 99 12 5 33 7 20（表长 6）

    int e;
    ListDelete(3, e);
    printf("删掉的是 %d\n", e);                       // 5
    PrintList();                                     // 99 12 33 7 20（表长 5）

    GetElem(2, e);
    printf("第 2 个元素是 %d\n", e);                  // 12
    printf("值 33 的位序是 %d\n", LocateElem(33));    // 3
    printf("值 404 的位序是 %d（0 表示没找到）\n", LocateElem(404));

    /* ---------- 复杂度小结 ----------
       按位取值 O(1) ｜ 按值查找 O(n) ｜ 插入 O(n) ｜ 删除 O(n)
       插入平均搬动 n/2 个元素，删除平均搬动 (n-1)/2 个：
       插入位置等概率取 1..n+1，搬动次数分别是 n, n-1, ..., 1, 0，
       平均 = (0+1+...+n)/(n+1) = n/2；删除同理得 (n-1)/2。 */
    return 0;
}

2.2.3 按位查找：O(1) 的随机存取

有了地址公式，按位查找就是「检查一下边界，然后把下标减一取出来」。 注意两个细节：一是位序转下标要减 1；二是越界必须挡在门外， 因为 data[i-1] 在 C++ 里不做任何检查，越界读是未定义行为 undefined behavior， 可能读到垃圾值，也可能直接把程序搞崩。

/* ==========================================================================
   顺序表的三种「读」操作：按位取值、按值查找、遍历打印
   --------------------------------------------------------------------------
   竞赛写法：依然是「全局数组 + 自由函数」，和上一段 seqlist.cpp 完全一致。

   这里最值得记住的一句话：
       按位取值是 O(1)，因为可以「算」出地址；按值查找是 O(n)，因为只能「比」。
   这就是顺序表被称为「随机存取结构」的原因。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
int n = 0;

/* ---------- 1) 按位取值 GetElem：位序 i → 下标 i-1，一步到位，O(1) ---------- */
bool GetElem(int i, int &e) {
    if (i < 1 || i > n) return false;   // 位序范围 1..n，注意不是 0..n-1
    e = a[i - 1];                       // 位序 → 下标：减 1
    return true;
}

/* 顺便看一眼「地址」是怎么算出来的：
   设首元素地址为 LOC(a[0])，每个元素占 L 字节，则
       LOC(a[i]) = LOC(a[0]) + i * L
   所以给定下标就能直接算出地址，不需要从头走一遍 —— 这就是 O(1) 的来源。 */

/* ---------- 2) 按值查找 LocateElem：只能从头挨个比，O(n) ---------- */
int LocateElem(int e) {
    for (int k = 0; k < n; ++k)
        if (a[k] == e) return k + 1;    // 返回位序，所以是 k+1
    return 0;                           // 0 = 没找到（位序从 1 起，0 不会被占用）
}

/* 平均查找长度 ASL：等概率下每个位置被查到的概率是 1/n，
   比较次数分别是 1, 2, ..., n，所以 ASL = (1+2+...+n)/n = (n+1)/2。 */

/* ---------- 3) 遍历打印 PrintList：逐个访问，O(n) ---------- */
void PrintList() {
    for (int k = 0; k < n; ++k) printf("%d ", a[k]);
    printf("（表长 %d）\n", n);
}

int main() {
    for (int x : {12, 5, 33, 7, 20}) a[n++] = x;    // 直接往表尾放，建表 O(n)

    PrintList();                        // 12 5 33 7 20（表长 5）

    int e;
    if (GetElem(3, e)) printf("第 3 个元素 = %d\n", e);          // 33
    printf("GetElem(9) 返回 %d（false 表示越界）\n", (int)GetElem(9, e));

    printf("第一个 7 的位序 = %d\n", LocateElem(7));              // 4
    printf("404 的位序 = %d（0 表示没找到）\n", LocateElem(404));

    /* ---------- 复杂度小结 ----------
       按位取值 O(1) ｜ 按值查找 O(n)（成功时 ASL=(n+1)/2）｜ 遍历 O(n) */
    return 0;
}

2.2.4 按值查找：为什么平均要比 (n+1)/2 次

按值查找没有捷径可走：地址公式只能算出「第 i 个在哪」，算不出「值等于 x 的那个在哪」。 所以只能从 a1 开始逐个比较。设查找的目标等概率地出现在任意位置， 比较次数分别为 1, 2, …, n，于是平均查找长度 ASL 为：

也就是说，平均要看一半的元素，时间复杂度 O(n)。 这也是顺序表相对哈希表（第 10 讲）最大的短板：按下标快如闪电，按值找慢如蜗牛。

2.2.5 插入：为什么平均要挪一半的元素

插入的难点在于「腾位置」。要在位序 i 处插入新元素， 就必须把原来 ai 及其后面的所有元素统统往后挪一格。 挪的时候有个关键顺序问题：必须从最后一个元素开始往前挪。 如果从 ai 开始往后挪，ai 会先把 ai+1 覆盖掉，等到要挪 ai+1 时原值已经没了—— 数据被自己吃掉，这就是典型的「覆盖丢失」。

下面用动画把这三步逐帧放慢，请特别注意「移动方向」与「移动次数计数器」：

现在把移动次数算清楚。在位序 i 处插入时，需要后移的元素是原来的 ai…an，共 n − i + 1 个：

假设 n + 1 个可插入位置等概率（概率各为 1/(n+1)）， 求平均移动次数 Einsert：

所以插入平均要搬 n/2 个元素，时间复杂度 O(n)。 这个结论的直觉解释是：平均来看，新元素会插在表的正中间，那么后面一半的元素都得往后挪一格。

2.2.6 删除：平均移动 (n−1)/2 次

删除是插入的逆操作：把位序 i 的元素拿掉，为了不让中间出现空洞（一旦有洞，地址公式就失效了）， 必须把 ai+1…an 整体向前挪一格。 这次的方向正好相反——从前往后挪，因为每个元素都是往已腾空的位置填，不会覆盖到还没处理的数据。

删除时要注意：表长减 1 只是让最后一个位置「逻辑上不存在」了，那块内存并没有被归还，也不需要 delete——顺序表是整块申请的，只能整块释放。

删除位序 i 的元素时，需要前移的是 ai+1…an， 共 n − i 个。i 取 1…n 等概率，于是：

/* ==========================================================================
   顺序表的插入与删除：移动方向、边界条件与复杂度
   --------------------------------------------------------------------------
   顺序表的插入/删除之所以慢，不是因为它「不会做」，而是因为要保持
   「逻辑相邻 = 物理相邻」这条规矩：一旦中间腾出一个空位或留下一个空洞，
   就必须把后面的元素整体搬一搬。

   两个必须记牢的方向：
      插入 —— 从后往前搬（不然会把还没搬的元素覆盖掉）
      删除 —— 从前往后搬（把空洞后面的元素依次补上来）
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
int n = 0;

void PrintList() {
    for (int k = 0; k < n; ++k) printf("%d ", a[k]);
    printf("（表长 %d）\n", n);
}

/* ---------- 插入：在位序 i 处插入 e，合法范围 1 <= i <= n+1 ----------
   i = n+1 表示插到表尾（不用搬元素）；i = 1 表示插到表头（要搬 n 个）。
   搬动次数 = n - i + 1，所以最坏 O(n)。 */
bool ListInsert(int i, int e) {
    if (i < 1 || i > n + 1) return false;      // 越界：注意上界是 n+1 不是 n
    if (n == N) return false;                  // 表满（静态数组才需要判，vector 会自动扩容）
    for (int k = n - 1; k >= i - 1; --k)       // 从后往前：a[n-1] → a[n]，依次后移
        a[k + 1] = a[k];
    a[i - 1] = e;
    ++n;
    return true;
}

/* ---------- 删除：删掉位序 i 的元素，用 e 带回，合法范围 1 <= i <= n ----------
   搬动次数 = n - i，所以最坏 O(n)。
   注意：删除后「表长减一」，最后那个位置虽然还留着旧值，但已经不属��表内了。 */
bool ListDelete(int i, int &e) {
    if (i < 1 || i > n) return false;
    e = a[i - 1];
    for (int k = i - 1; k < n - 1; ++k)        // 从前往后：把后面的元素依次往前补
        a[k] = a[k + 1];
    --n;
    return true;
}

int main() {
    for (int x : {12, 5, 33, 7, 20}) ListInsert(n + 1, x);   // 全都插到表尾，建表 O(n)
    PrintList();                     // 12 5 33 7 20（表长 5）

    ListInsert(1, 99);               // 插到表头：5 个元素全部后移一格
    PrintList();                     // 99 12 5 33 7 20（表长 6）

    ListInsert(n + 1, 88);           // 插到表尾：一次搬动都不需要
    PrintList();                     // 99 12 5 33 7 20 88（表长 7）

    int e;
    ListDelete(3, e);
    printf("删掉位序 3 的元素：%d\n", e);      // 5
    PrintList();                     // 99 12 33 7 20 88（表长 6）

    printf("越界删除 ListDelete(99) 返回 %d\n", (int)ListDelete(99, e));   // 0

    /* ---------- 复杂度分析（考点） ----------
       插入：位序 i 处插入要后移 n-i+1 个元素；
             等概率取 i = 1..n+1，平均搬动
             (n + (n-1) + ... + 1 + 0) / (n+1) = n/2 个 → O(n)
       删除：位序 i 处删除要前移 n-i 个元素；
             等概率取 i = 1..n，平均搬动
             ((n-1) + (n-2) + ... + 1 + 0) / n = (n-1)/2 个 → O(n)

       一句话记忆：顺序表「查得快、改得慢」——
       按位取值 O(1)，插入删除平均要搬一半元素。 */
    return 0;
}

2.2.7 表尾插入的均摊 O(1)：扩容账要这样算

看到 grow() 里那个 for 循环，很多人第一反应是： 「插入不是 O(n) 吗？怎么又说表尾插入是 O(1)？」 这里要区分单次操作的代价和均摊代价 amortized cost。

假设容量从 1 开始翻倍，连续在表尾插入 n 个元素。 触发扩容的时刻是容量为 1, 2, 4, 8, …, n/2 的时候， 每次扩容要搬的元素的个数恰好等于当时的容量，于是总搬运量为：

也就是说，插入 n 个元素的总搬运次数不到 n 次，分摊到每次插入上不到 1 次。 再加上每次插入本身的赋值操作，平均每次插入只做了常数次工作，所以是 O(1)。 这就是均摊分析 amortized analysis 的典型例子： 偶尔一次很贵（O(n)），但贵的次数极少，长期平均下来很便宜。

2.2.8 顺序表的优缺点小结

2.3 单链表：把结点散落在堆上，用指针串起来

顺序表的两条硬伤——「必须要一整块连续内存」和「插入删除要成片搬元素」—— 都来自同一个决定：用物理位置的相邻来表示逻辑关系的相邻。 链表把这个决定反过来做：元素爱放哪放哪，逻辑上的「下一个」用一个指针明确写出来。

这样一来，插入一个元素就不再需要挪动别人了，只要改两根指针； 代价是：每个元素必须额外带一个指针（空间开销变大）， 而且因为地址不再连续，下标访问彻底失效——想找第 100 个元素，只能从表头数 99 次。

2.3.1 结点结构：数据域 + 指针域

链表里存放一个元素的单元叫结点 node，它由两部分组成： 数据域 data field 存元素本身，指针域 pointer field 存「下一个结点在哪」。 在 C++ 里就是一个自引用的结构体：

这一行代码有个著名的坑：Node* next; 里的 Node 此时还没定义完， 为什么能编译通过？因为指针的大小是固定的（64 位平台 8 字节）， 编译器不需要知道 Node 的完整布局就能声明指向它的指针，这叫不完全类型 incomplete type。 但如果你写成 Node next;（少一个星号），编译器立刻报「不完整类型」错误—— 因为它无法算出一个「包含自己的自己」有多大。这个错误信息考试和作业里都非常常见。

2.3.2 头指针 / 头结点 / 首元结点：三个词，三样东西

这是本章最高频的易错点，没有之一。很多同学代码写不对，就是因为把这三个概念搅成了一锅粥。 先把定义摆清楚：

头指针 head pointer

一个指针变量，它指向链表的第一个结点。它是链表的「身份证」—— 只要拿到头指针，整条链表就能找到；头指针没了，整条链就泄漏了。 头指针一定不为空（哪怕表是空的，它也指向头结点）。

头结点 head node / 哑结点 dummy node

一个真实存在的结点，放在首元结点之前，它的数据域通常不使用（可以存表长等附加信息）， 指针域指向首元结点。引入它是为了让「空表」和「非空表」、「第一个位置」和「其他位置」 用同一套代码处理，不用特判。

首元结点 first element node

链表中真正存放第一个数据元素 a1 的结点，也就是 head->next 指向的那个结点。空表时它不存在（head->next == nullptr）。

2.3.3 头插法与尾插法建表：一个逆序，一个正序

建立链表时，每个新结点都要「挂」到链上。挂的位置不同，就产生了两种建表法： 头插法每次都插在头结点之后（插在表头），尾插法每次都接在尾巴后面。 它们的差别不只是顺序，还有是否需要额外的尾指针。

/* ==========================================================================
   单链表的建立 —— 头插法与尾插法（算法竞赛写法）
   --------------------------------------------------------------------------
   竞赛里写链表的标准姿势：
       · 用 struct 描述「结点长什么样」（数据域 + 指针域），这是知识点本身
       · 用全局指针存表头，操作写成自由函数（不做类封装）
       · 需要临时结点时直接 new，程序结束就回收，比赛里不用手动 delete

   两个必须区分的概念（高频易错点）：
       头指针 head —— 指向链表的第一个结点，它本身不是结点，是「入口」
       首元结点    —— 链表中真正存第一个数据元素的那个结点
       头结点      —— 为了简化操作，在首元结点前面附加的一个「哑结点」，
                      它不存数据，next 指向首元结点。空表时 head->next == NULL。
   下面用「带头结点」的版本：插入删除时不用特判「在表头操作」这种边界。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {               // 结点：数据域 + 指针域
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head = nullptr;       // 头指针：指向头结点（哑结点）

/* ---------- 建表：只要头结点，链表就是空表 ---------- */
void InitList() {
    head = new Node();      // 头结点不存数据
}

/* ---------- 头插法：每次插在首元结点前面，O(1) ----------
   顺序会反过来！输入 1 2 3，链表里是 3 2 1。 */
void PushFront(int x) {
    Node *p = new Node(x);              // 1) 造新结点
    p->nxt = head->nxt;                 // 2) 先连：新结点接上原来的首元结点
    head->nxt = p;                      // 3) 后断：头结点改指向新结点
    /* 这两句的顺序不能反！先写 head->nxt = p 就把原来的链表弄丢了 */
}

/* ---------- 尾插法：维护一个尾指针 tail，插到表尾也是 O(1) ----------
   顺序和输入一致，这是做题时更常用的建表方式。 */
Node *tail = nullptr;
void PushBack(int x) {
    Node *p = new Node(x);
    tail->nxt = p;                      // 接到尾巴后面
    tail = p;                           // 更新尾指针
}

void InitListWithTail() {
    head = new Node();
    tail = head;                        // 空表时尾指针也指向头结点
}

void PrintList(const char *title) {
    printf("%s：", title);
    for (Node *p = head->nxt; p != nullptr; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL（不含头结点）\n");
}

int main() {
    /* ---------- 头插法 ---------- */
    InitList();
    for (int x : {1, 2, 3, 4, 5}) PushFront(x);
    PrintList("头插 1..5");               // 5 -> 4 -> 3 -> 2 -> 1 -> NULL

    /* ---------- 尾插法 ---------- */
    InitListWithTail();
    for (int x : {1, 2, 3, 4, 5}) PushBack(x);
    PrintList("尾插 1..5");               // 1 -> 2 -> 3 -> 4 -> 5 -> NULL

    /* ---------- 复杂度与对比 ----------
       头插 O(1)、尾插（带尾指针）O(1)、建立长度为 n 的表整体 O(n)。
       对比顺序表：建表也是 O(n)，但顺序表插入要搬元素，链表只改指针。

       竞赛里什么时候用链表？
       很少直接用！多数题目用「数组模拟链表」（见第 02 讲静态链表一节）
       或链式前向星（第 08 讲），因为 new 慢、指针跳转还会让 cache 命中率变差。 */
    return 0;
}

2.3.4 按位查找与按值查找：都是 O(n)

链表失去了地址公式，按位查找也不得不从头数过去。 想找第 i 个结点，就要从首元结点开始走 i − 1 步， 因此时间复杂度是 O(n)，而不是顺序表的 O(1)。 按值查找同样是 O(n)，但要注意它与顺序表的区别： 顺序表的按值查找最坏是「比较 n 次」，链表的按值查找最坏是「比较 n 次 + 走 n 步指针」， 常数因子更大，实际跑起来更慢（还有缓存不友好的问题）。

/* ==========================================================================
   单链表的查找：按位查找 与 按值查找
   --------------------------------------------------------------------------
   链表和顺序表最大的差别就在查找上：
       顺序表按位取值 O(1)（能直接算出地址）
       链表按位取值 O(n)（只能顺着指针一个个走，因为结点散落在内存各处）

   所以「随机存取」这个词只属于顺序存储结构，链表是「顺序存取」。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head;                 // 头指针（指向头结点）

void InitList() { head = new Node(); }

void PushBack(int x) {      // 尾插建表
    Node *p = head;
    while (p->nxt) p = p->nxt;          // 这里为了代码短，每次从头找尾：O(n)
    p->nxt = new Node(x);
}

/* ---------- 按位查找 GetElem：返回第 i 个结点的指针，O(n) ----------
   约定：i 从 1 开始。i 越界返回 nullptr。
   注意 p 从 head->nxt 起步 —— 跳过头结点，因为它不算「第 1 个元素」。 */
Node *GetElem(int i) {
    if (i < 1) return nullptr;
    Node *p = head->nxt;                // p 指向首元结点
    int j = 1;
    while (p && j < i) { p = p->nxt; ++j; }
    return p;                           // 走到第 i 个就返回；中途变 NULL 说明 i 越界
}

/* ---------- 按值查找 LocateElem：返回第一个值为 e 的结点指针 ---------- */
Node *LocateElem(int e) {
    for (Node *p = head->nxt; p; p = p->nxt)
        if (p->val == e) return p;
    return nullptr;
}

/* ---------- 求表长：O(n)。若经常用，可以额外维护一个 len 变量变成 O(1) ---------- */
int Length() {
    int n = 0;
    for (Node *p = head->nxt; p; p = p->nxt) ++n;
    return n;
}

void PrintList(const char *title = "") {
    printf("%s：", title);
    for (Node *p = head->nxt; p; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL\n");
}

int main() {
    InitList();
    for (int x : {12, 5, 33, 7, 20}) PushBack(x);
    PrintList("链表");                    // 12 -> 5 -> 33 -> 7 -> 20 -> NULL

    printf("表长 = %d\n", Length());       // 5

    Node *p = GetElem(3);
    printf("第 3 个结点 = %s\n", p ? to_string(p->val).c_str() : "越界");   // 33

    p = GetElem(9);
    printf("第 9 个结点 = %s\n", p ? to_string(p->val).c_str() : "越界（返回 nullptr）");

    p = LocateElem(7);
    printf("值 7 的结点 = %s\n", p ? to_string(p->val).c_str() : "没找到");  // 7

    p = LocateElem(404);
    printf("值 404 的结点 = %s\n", p ? to_string(p->val).c_str() : "没找到（返回 nullptr）");

    /* ---------- 结论 ----------
       按位查找 O(n)、按值查找 O(n)、求表长 O(n)（可优化到 O(1)）。
       链表唯一「快」的地方是：已知某个结点时插入删除是 O(1)，因为它不用搬元素。 */
    return 0;
}

2.3.5 插入结点：为什么必须「先连后断」

链表插入的灵魂是两根指针的赋值顺序。设 p 是第 i−1 个结点 （新结点的前驱），s 是刚 new 出来的新结点，标准写法是：

为什么不能反过来？关键在于 p->next 这个「唯一的路标」。 它本来记着 ai 的地址，是通往链表后半段唯一的线索。 如果先执行 p->next = s;，这个路标就被改写成新结点 s 了； 于是接下来执行 s->next = p->next; 时读到的其实是 s 自己， 结果是 s->next == s——新结点指向自己，形成一个孤立的自环， 原来的 ai 及后面整段链表全部丢失，而且再也没有指针能找到它们， 造成彻底的内存泄漏。

光看图还不够，请一定亲手点一遍下面的动画——它会一帧一帧地演示 p 如何走到第 i−1 个结点、两根指针如何先后改写，最后还专门用一段「错误顺序」的分支告诉你断链长什么样。

2.3.6 删除结点：找前驱，以及一个 O(1) 的技巧

删除位序 i 的结点，需要做三件事： 找到它的前驱 p（第 i−1 个结点）、 让 p 跨过被删结点、释放被删结点的内存。 代码只有三行，但每一行都有讲究：

为什么必须先 q = p->next 保存下来？因为一旦执行 p->next = q->next， 被删结点的地址就再也拿不到了，delete 无从谈起，那块内存就永久泄漏。 同理，在「整表删除」的循环里也必须先保存 p->next 再 delete p。

按位删除要 O(n) 找前驱。那如果题目直接给你一个指向待删结点的指针 p， 要求 O(1) 删掉它呢？在单链表里有一个巧妙的「后继覆盖法」（偷梁换柱）：

既然找不到前驱，那就干脆不删自己，而是把后继的值抄到自己身上，然后删掉后继。 从外面看效果完全一样。这个方法有两个致命限制，面试时经常被追问：

下面的动画把「按位删除」与「后继覆盖法」两种情形都演一遍，注意观察 p、q 两个指针的落点：

/* ==========================================================================
   单链表的删除 —— 为什么删除必须知道「前驱」
   --------------------------------------------------------------------------
   要在链表中摘掉结点 p，得让 p 的前驱直接指向 p 的后继：
       pre->nxt = p->nxt;   // 绕开 p
   也就是说：**插入/删除都要动前驱的指针**，所以「找到前驱」是关键。

   竞赛里必备的一个技巧：如果只给了要删的结点 p、没给前驱，怎么办？
       —— 把后继的数据「复制」到 p 上，再删掉后继（下一段代码演示）。
       这个方法不适用于「删除尾结点」（尾结点没有后继），要特判。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head;

void InitList() { head = new Node(); }

void PushBack(int x) {
    Node *p = head;
    while (p->nxt) p = p->nxt;
    p->nxt = new Node(x);
}

/* ---------- 取第 i 个结点（i 从 1 起），越界返回 nullptr ---------- */
Node *GetElem(int i) {
    if (i < 1) return nullptr;
    Node *p = head->nxt;
    for (int j = 1; p && j < i; ++j) p = p->nxt;
    return p;
}

/* ---------- 删除第 i 个结点：先找第 i-1 个（前驱），再摘下第 i 个 ----------
   用 e 带回被删的值，返回是否成功。O(n)（时间花在找前驱上）。 */
bool ListDelete(int i, int &e) {
    Node *pre = head;                       // 从「头结点」开始找前驱，这样 i=1 也能统一处理
    for (int j = 1; j < i && pre->nxt; ++j) pre = pre->nxt;
    if (pre->nxt == nullptr) return false;  // i 超过表长
    Node *p = pre->nxt;
    e = p->val;
    pre->nxt = p->nxt;                      // 摘掉 p：前驱跨过 p
    delete p;                               // 释放这个结点（竞赛里也可以不写）
    return true;
}

/* ---------- 删除「值为 x」的第一个结点：同样要找前驱 ---------- */
bool DeleteValue(int x) {
    for (Node *pre = head; pre->nxt; pre = pre->nxt) {
        if (pre->nxt->val == x) {
            Node *p = pre->nxt;
            pre->nxt = p->nxt;
            delete p;
            return true;
        }
    }
    return false;
}

/* ---------- 进阶：只给结点 p（不给前驱），O(1) 删掉它 ----------
   思路：把 p 的后继「搬」到 p 身上，然后删掉后继。
   限制：p 不能是尾结点（尾结点没有后继可搬）。 */
bool DeleteNodeSelf(Node *p) {
    if (p == nullptr || p->nxt == nullptr) return false;   // 尾结点不适用
    Node *q = p->nxt;
    p->val = q->val;                        // 后继的值复制过来
    p->nxt = q->nxt;                        // 跨过后继
    delete q;
    return true;
}

void PrintList(const char *title = "") {
    printf("%s", title);
    for (Node *p = head->nxt; p; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL\n");
}

int main() {
    InitList();
    for (int x : {12, 5, 33, 7, 20}) PushBack(x);
    PrintList("原链表 ");                 // 12 -> 5 -> 33 -> 7 -> 20 -> NULL

    int e;
    ListDelete(1, e);
    printf("删掉第 1 个：%d\n", e);        // 12（删表头也要走「找前驱」这条路，头结点帮了大忙）
    PrintList("现在   ");                 // 5 -> 33 -> 7 -> 20 -> NULL

    ListDelete(3, e);
    printf("删掉第 3 个：%d\n", e);        // 7
    PrintList("现在   ");                 // 5 -> 33 -> 20 -> NULL

    printf("DeleteValue(33) 返回 %d\n", (int)DeleteValue(33));
    PrintList("现在   ");                 // 5 -> 20 -> NULL

    printf("ListDelete(9) 返回 %d\n", (int)ListDelete(9, e));   // 0（越界）

    /* ---- 演示 O(1) 删除：只给结点指针，不给前驱 ---- */
    InitList();
    for (int x : {1, 2, 3, 4, 5}) PushBack(x);
    Node *p = GetElem(3);                 // 拿到第 3 个结点（值 3）
    DeleteNodeSelf(p);
    PrintList("O(1) 删掉第 3 个后 ");      // 1 -> 2 -> 4 -> 5 -> NULL

    /* ---------- 结论 ----------
       删除第 i 个结点 O(n)（找前驱），已给前驱时 O(1)。
       对比顺序表删除平均搬 (n-1)/2 个元素：链表只改两个指针，这是它唯一的优势。 */
    return 0;
}

2.3.7 单链表的完整实现 SinglyList

把前面的片段拼起来，下面是一份可以直接编译运行、覆盖全部基本操作的完整单链表实现。 它带一个尾指针 tail，因此表尾追加是 O(1)；同时保留了头结点，所有位置的操作都统一。 建议把这段代码抄进 IDE 单步走一遍，尤其是 ListInsert 与 Clear。

/* ==========================================================================
   单链表完整实现 —— 一份可以直接抄去比赛的模板
   --------------------------------------------------------------------------
   把前面几段的东西合起来：建表、求长、按位/按值查找、插入、删除、反转、打印。
   全部用「全局头指针 + 自由函数」的竞赛写法，不用类。

   约定（全课件统一）：
       · 带头结点（哑结点），空表时 head->nxt == NULL
       · 位序 i 从 1 开始，对应链表中的第 i 个数据结点（不含头结点）
       · 函数返回 bool 表示成败，越界就是 false，不抛异常
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head;                  // 头指针

/* ==================== 基本操作 ==================== */

void InitList() { head = new Node(); }

int Length() {
    int n = 0;
    for (Node *p = head->nxt; p; p = p->nxt) ++n;
    return n;
}

void PushFront(int x) {                  // 头插 O(1)
    head->nxt = new Node(x, head->nxt);
}

void PushBack(int x) {                   // 尾插 O(n)（没维护尾指针）
    Node *p = head;
    while (p->nxt) p = p->nxt;
    p->nxt = new Node(x);
}

Node *GetElem(int i) {                   // 按位查找 O(n)，i 从 1 起
    if (i < 1) return nullptr;
    Node *p = head->nxt;
    for (int j = 1; p && j < i; ++j) p = p->nxt;
    return p;
}

Node *LocateElem(int e) {                // 按值查找 O(n)
    for (Node *p = head->nxt; p; p = p->nxt)
        if (p->val == e) return p;
    return nullptr;
}

bool ListInsert(int i, int e) {          // 在位序 i 处插入：先找前驱 O(n)
    Node *pre = head;
    for (int j = 1; j < i && pre->nxt; ++j) pre = pre->nxt;
    if (i < 1 || (i > 1 && pre->nxt == nullptr)) return false;   // i 越界
    pre->nxt = new Node(e, pre->nxt);    // 新结点接上后继，前驱再接新结点
    return true;
}

bool ListDelete(int i, int &e) {         // 删除位序 i：先找前驱 O(n)
    Node *pre = head;
    for (int j = 1; j < i && pre->nxt; ++j) pre = pre->nxt;
    if (pre->nxt == nullptr) return false;
    Node *p = pre->nxt;
    e = p->val;
    pre->nxt = p->nxt;
    delete p;
    return true;
}

/* ==================== 竞赛常考的链表操作 ==================== */

/* 1) 反转链表（迭代版）：pre / cur / nxt 三个指针依次翻转，O(n)、O(1) 空间 */
void Reverse() {
    Node *pre = nullptr, *cur = head->nxt;
    while (cur) {
        Node *nxt = cur->nxt;            // 先存下后继，否则翻完就找不到了
        cur->nxt = pre;                  // 翻转指针
        pre = cur;                       // 三个指针整体后移
        cur = nxt;
    }
    head->nxt = pre;                     // 头结点指向新的首元结点
}

/* 2) 找中间结点（快慢指针）：slow 走 1 步、fast 走 2 步，fast 到头时 slow 在中间 */
Node *Middle() {
    Node *slow = head->nxt, *fast = head->nxt;
    while (fast && fast->nxt) { slow = slow->nxt; fast = fast->nxt->nxt; }
    return slow;                         // 偶数个结点时返回「中间偏右」那个
}

/* 3) 判断是否有环（Floyd 判环），返回相遇点；无环返回 nullptr */
Node *HasCycle() {
    Node *slow = head->nxt, *fast = head->nxt;
    while (fast && fast->nxt) {
        slow = slow->nxt;
        fast = fast->nxt->nxt;
        if (slow == fast) return slow;
    }
    return nullptr;
}

void PrintList(const char *title = "") {
    printf("%s：", title);
    for (Node *p = head->nxt; p; p = p->nxt) printf("%d -> ", p->val);
    printf("NULL（长度 %d）\n", Length());
}

int main() {
    InitList();
    for (int x : {1, 2, 3, 4, 5, 6}) PushBack(x);
    PrintList("初始");

    ListInsert(1, 0);                 // 插到表头
    ListInsert(4, 99);                // 插到中间
    PrintList("插入 0 到表头、99 到第 4 位");

    int e;
    ListDelete(4, e);
    printf("删掉 %d\n", e);
    PrintList("删除后");

    printf("表长 = %d，中间结点 = %d\n", Length(), Middle()->val);

    Reverse();
    PrintList("反转后");

    printf("是否有环：%s\n", HasCycle() ? "有" : "无");

    /* 人为造一个环：把尾结点指回第 3 个结点 */
    Node *tail = head->nxt;
    while (tail->nxt) tail = tail->nxt;
    tail->nxt = GetElem(3);
    printf("造环后再判：%s\n", HasCycle() ? "有环（快慢指针相遇）" : "无环");

    /* ---------- 复杂度汇总（考点） ----------
       建表 O(n) ｜ 求长 O(n) ｜ 按位查找 O(n) ｜ 按值查找 O(n)
       已知前驱时插入/删除 O(1) ｜ 否则 O(n)（时间花在找前驱）
       反转 O(n) 时间、O(1) 空间 ｜ 判环 O(n) 时间、O(1) 空间
       对比顺序表：链表牺牲了随机存取（O(1) → O(n)），换来插入删除不用搬元素。 */
    return 0;
}

2.3.8 反转单链表：三道指针小题的「母题」

反转链表是链表题的总入口，因为它强迫你同时管理三根指针。 迭代写法的核心只有一句：用 pre 记住已反转部分的头，用 cur 指向待处理结点， 每轮先把 cur->next 存档到 nxt，然后把 cur->next 指向 pre。 存档这一步必须最先做，道理和插入的「先连后断」完全一样——不存档就丢链。

下面的动画把每一轮的四步操作完整放慢，请对照上图观察三条边的颜色变化：

// reverse_list.cpp —— 单链表反转的三种写法（均为 O(n) 时间）
#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} };

/* ---------- 写法一：迭代三指针。空间 O(1)，工程首选 ---------- */
Node* ReverseIter(Node* first) {          // 约定：first 是首元结点指针（不带头结点）
    Node* pre = nullptr;                  // 反转后，新链的尾结点的 next 应为 NULL
    Node* cur = first;
    while (cur) {
        Node* nxt = cur->next;            // ① 存档：不存就等于把后半段扔了
        cur->next = pre;                  // ② 翻转当前这条边
        pre = cur;                        // ③ pre 前移
        cur = nxt;                        // ④ cur 前移
    }
    return pre;                           // 循环结束 cur == NULL，pre 指向原尾结点 = 新表头
}

/* ---------- 写法二：递归。空间 O(n)（递归栈深度等于表长） ---------- */
Node* ReverseRec(Node* first) {
    if (!first || !first->next) return first;     // 空表 / 单结点：无需反转
    Node* newHead = ReverseRec(first->next);      // 先把后面全部翻好，返回新表头
    first->next->next = first;                    // 原来的后继反过来指向自己
    first->next = nullptr;                        // 自己变成新链的尾结点
    return newHead;                               // 新表头一路上传
}

/* ---------- 写法三：就地头插（带头结点版本，考试常考） ---------- */
void ReverseInPlace(Node* head) {         // head 是头结点，不存数据
    Node* p = head->next;                 // 从首元结点开始
    head->next = nullptr;                 // 先断开：头结点变成新链的「哨兵尾」
    while (p) {
        Node* q = p->next;                // ① 存档
        p->next = head->next;             // ② 头插：接到新链最前面
        head->next = p;
        p = q;                            // ③ 取下一个
    }
}

/* ---------- 测试 ---------- */
Node* Build(const int a[], int n) {
    Node dummy; Node* r = &dummy;
    for (int i = 0; i < n; ++i) { r->next = new Node(a[i]); r = r->next; }
    return dummy.next;
}
void Show(const char* tag, Node* p) {
    cout << tag;
    for (; p; p = p->next) cout << p->data << " ";
    cout << endl;
}
int main() {
    int a[] = {1, 2, 3, 4, 5};
    Show("原链表  : ", Build(a, 5));
    Show("迭代反转: ", ReverseIter(Build(a, 5)));
    Show("递归反转: ", ReverseRec(Build(a, 5)));

    Node* h = new Node();                      // 带头结点版本
    Node* r = h;
    for (int i = 0; i < 5; ++i) { r->next = new Node(a[i]); r = r->next; }
    ReverseInPlace(h);
    Show("就地头插: ", h->next);
    return 0;
}

2.3.9 快慢指针（一）：求中间结点与倒数第 k 个结点

快慢指针（也叫龟兔赛跑）是链表题的第二把万能钥匙： 让 fast 每次走 2 步、slow 每次走 1 步， 那么 fast 走过的路程永远是 slow 的两倍。 当 fast 到达表尾时，slow 恰好走了一半——这就是中间结点。 整个算法只遍历一遍，时间 O(n)、空间 O(1)，比「先数长度再走一半」的两趟扫描优雅得多。

「倒数第 k 个」是同一个思想的应用：先让 fast 领先 slow 恰好 k 步， 然后两者同速前进；当 fast 走到 NULL（尾结点之后）时， slow 与表尾的距离正好是 k，即 slow 指向倒数第 k 个结点。

// fast_slow.cpp —— 快慢指针：求中间结点、倒数第 k 个结点
#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} };

/* 中间结点：fast 每次 2 步，slow 每次 1 步。时间 O(n)，空间 O(1) */
Node* MiddleNode(Node* first) {
    Node* slow = first;
    Node* fast = first;
    while (fast && fast->next) {          // 两个条件缺一不可：
        slow = slow->next;                //   fast 判空防止 fast->next 解空指针；
        fast = fast->next->next;          //   fast->next 判空保证能安全走两步。
    }
    return slow;                          // 奇数个结点返回正中；偶数个结点返回「后中间」
}
/* 如果想在偶数个结点时返回「前中间」，把条件改成：
   while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } */

/* 倒数第 k 个结点：fast 先走 k 步拉开差距，再同步前进 */
Node* KthFromEnd(Node* first, int k) {
    if (k < 1) return nullptr;
    Node* fast = first;
    for (int i = 0; i < k; ++i) {         // fast 领先 k 步
        if (!fast) return nullptr;        // k 比表长还大，不存在倒数第 k 个
        fast = fast->next;
    }
    Node* slow = first;
    while (fast) {                        // 同步走，直到 fast 出表尾
        slow = slow->next;
        fast = fast->next;
    }
    return slow;                          // fast 走了 n-k 步，slow 从 1 走到 n-k+1，即倒数第 k 个
}

Node* Build(const int a[], int n) {
    Node dummy; Node* r = &dummy;
    for (int i = 0; i < n; ++i) { r->next = new Node(a[i]); r = r->next; }
    return dummy.next;
}
int main() {
    int a[] = {1, 2, 3, 4, 5};
    int b[] = {1, 2, 3, 4, 5, 6};
    cout << "5 个结点的中间 = " << MiddleNode(Build(a, 5))->data << endl;   // 3
    cout << "6 个结点的中间 = " << MiddleNode(Build(b, 6))->data << endl;   // 4（后中间）
    cout << "倒数第 2 个 = " << KthFromEnd(Build(a, 5), 2)->data << endl;    // 4
    cout << "倒数第 1 个 = " << KthFromEnd(Build(a, 5), 1)->data << endl;    // 5
    cout << "倒数第 9 个 = " << (KthFromEnd(Build(a, 5), 9) ? "存在" : "不存在") << endl;
    return 0;
}

2.3.10 快慢指针（二）：Floyd 判环与环入口的数学推导

Floyd 判环算法（龟兔赛跑算法）回答两个问题： 链表里有没有环？如果有，环的入口在哪？它的做法依然是快慢指针： 如果链表无环，fast 一定会先撞上 NULL； 如果有环，fast 会先进环并且在环里绕圈，由于 slow 每轮只前进 1 步， fast 相对 slow 的速度是每轮 1 步，所以 fast 一定会追上 slow，而绝不会跨过去。

「绝不会跨过去」这一条值得单独强调，因为很多人第一反应是「快指针会不会直接跳过慢指针」：

接下来是本章最漂亮的一段数学。设：

a

从表头（首元结点）到环入口的步数，也就是「尾巴」的长度。

b

环的长度（环内结点个数）。

c

从环入口沿前进方向走到相遇点的步数，显然 0 ≤ c < b。

t

从出发到相遇，slow 走过的步数。

相遇时两件事同时成立：

②−① 得 t = m·b，代回 ① 得：

这个式子的含义是：从表头走 a 步，与从相遇点走 a 步，落点是同一个结点。 因为从相遇点出发，先走 b − c 步就回到了环入口， 再多绕 (m−1) 整圈还是回到环入口。 于是算法第二步就出来了：让一个指针从表头出发、另一个从相遇点出发，同速前进，它们相遇的地方就是环入口。

下面的动画用一条带环的链表演示全过程：slow 每步 1 格、fast 每步 2 格， 相遇之后进入第二阶段——两个指针分别从表头和相遇点同步出发，最终在入口会合。

// floyd_cycle.cpp —— 判环、求环入口、求环长（全部 O(n) 时间 / O(1) 空间）
#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} };

/* 第一问：有没有环？有则返回相遇结点，无则返回 nullptr */
Node* HasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;                    // 每轮 1 步
        fast = fast->next->next;              // 每轮 2 步
        if (slow == fast) return slow;        // 相遇 ⇒ 有环
    }
    return nullptr;                           // fast 撞到 NULL ⇒ 无环
}

/* 第二问：环入口在哪？依据 a = (m-1)b + (b-c) */
Node* CycleEntry(Node* head) {
    Node* meet = HasCycle(head);
    if (!meet) return nullptr;                // 无环，谈不上入口
    Node* p = head;                           // 一个从表头出发
    while (p != meet) {                       // 另一个从相遇点出发，同速前进
        p = p->next;
        meet = meet->next;
    }
    return p;                                 // 相遇处即入口
}

/* 第三问：环长是多少？从相遇点绕一圈回到自己 */
int CycleLength(Node* meet) {
    if (!meet) return 0;
    int n = 1;
    for (Node* p = meet->next; p != meet; p = p->next) ++n;
    return n;
}
/* 附加：整条链的结点总数（尾巴 a 步 + 环长 b） */
int TotalLength(Node* head) {
    Node* entry = CycleEntry(head);
    if (!entry) { int n = 0; for (Node* p = head; p; p = p->next) ++n; return n; }
    int a = 0;
    for (Node* p = head; p != entry; p = p->next) ++a;
    return a + CycleLength(entry);
}

int main() {
    /* 构造： 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (回到 4)，即 a = 3, b = 5 */
    Node* nodes[9];
    for (int i = 1; i <= 8; ++i) nodes[i] = new Node(i);
    for (int i = 1; i < 8; ++i) nodes[i]->next = nodes[i + 1];
    nodes[8]->next = nodes[4];                 // 造环：8 指回 4

    Node* meet = HasCycle(nodes[1]);
    cout << (meet ? "有环，相遇于 " + to_string(meet->data) : "无环") << endl;
    Node* entry = CycleEntry(nodes[1]);
    cout << "环入口 = " << (entry ? to_string(entry->data) : "无") << endl;   // 4
    cout << "环长 = " << CycleLength(entry) << endl;                          // 5
    cout << "总长 = " << TotalLength(nodes[1]) << endl;                       // 8
    return 0;
}

2.3.11 合并两个有序链表

合并两个递增有序的单链表，是「归并排序」在链表上的缩影，也是「哑结点技巧」的最佳示范。 思路是双指针 + 尾插：a、b 分别指向两条链的待比较结点， 谁的当前值小就把谁摘下来接到结果链的尾部，然后该指针后移。 当一条链走完，把另一条整段接上即可——这一步是 O(1) 的，不需要逐个搬运。

这里我们用一个栈上的哑结点 Node dummy; 作为结果链的临时头结点， 它的作用与头结点一模一样：让「第一个结点」和「后续结点」用同一句 r->next = ...; r = r->next; 处理，省掉一堆 if (result == NULL)。 最后返回 dummy.next 即可，注意 dummy 是局部变量，函数返回后失效， 但 dummy.next 指向的是堆上的结点，完全安全。

// merge_sorted.cpp —— 合并两个递增有序单链表（复用原结点，不额外分配内存）
#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} };

/* 返回合并后的首元结点指针。时间 O(m+n)，空间 O(1) */
Node* MergeSorted(Node* a, Node* b) {
    Node  dummy;                          // 栈上的哑结点：只借用它的 next，不参与结果
    Node* r = &dummy;                     // r 始终指向结果链的尾结点
    while (a && b) {
        if (a->data <= b->data) {          // 取等号可保证「稳定性」：a 中相等元素排在前面
            r->next = a;
            a = a->next;
        } else {
            r->next = b;
            b = b->next;
        }
        r = r->next;                      // 尾指针后移
    }
    r->next = a ? a : b;                  // 剩下那一段直接整条挂上，O(1)
    return dummy.next;                    // dummy 在栈上，但它指向的结点在堆上，安全
}

/* 如果你希望「不破坏原链表」，就得 new 新结点，空间变成 O(m+n)，这是一个常见追问 */
Node* MergeCopy(Node* a, Node* b) {
    Node dummy; Node* r = &dummy;
    while (a && b) {
        if (a->data <= b->data) { r->next = new Node(a->data); a = a->next; }
        else                    { r->next = new Node(b->data); b = b->next; }
        r = r->next;
    }
    for (Node* p = a ? a : b; p; p = p->next) { r->next = new Node(p->data); r = r->next; }
    return dummy.next;
}

Node* Build(const int arr[], int n) {
    Node dummy; Node* r = &dummy;
    for (int i = 0; i < n; ++i) { r->next = new Node(arr[i]); r = r->next; }
    return dummy.next;
}
void Show(Node* p) { for (; p; p = p->next) cout << p->data << " "; cout << endl; }

int main() {
    int x[] = {1, 3, 5, 7, 9};
    int y[] = {2, 4, 6, 8};
    Show(MergeSorted(Build(x, 5), Build(y, 4)));   // 1 2 3 4 5 6 7 8 9
    int u[] = {1, 1, 3};
    int v[] = {1, 2, 3};
    Show(MergeSorted(Build(u, 3), Build(v, 3)));   // 1 1 1 2 3 3（相等时先取 a，稳定）
    return 0;
}

2.3.12 删除重复元素、求交集与并集

这三个操作本质上是「遍历 + 比较 + 摘链」的组合。 最关键的分支判断是：什么情况下指针才能前进。 删除重复元素时，一旦发现 p->data == p->next->data， 我们删掉的是 p->next，此时 p 本身不能动—— 因为新的后继可能还是重复值（想想 1,1,1,2）。 这是一个非常经典的「删了之后不要前进」的坑。

求交集与并集都要求两条链已经有序（无序则要先排序或用哈希，复杂度另算）， 然后采用与归并完全相同的双指针同步推进策略： 相等就是交集元素；不等时把小的那个推进一格。 并集则是归并 + 跳过相等元素。

// unique_and_set.cpp —— 删除重复元素、求交集、求并集
#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int d = 0, Node* n = nullptr) : data(d), next(n) {} };

/* 有序单链表去重：时间 O(n)，空间 O(1) */
void UniqueSorted(Node* first) {
    Node* p = first;
    while (p && p->next) {
        if (p->data == p->next->data) {
            Node* q = p->next;                // 删掉后面的重复者
            p->next = q->next;
            delete q;
            /* 注意：这里 p 不前进！因为新的 p->next 可能还是同一个值 */
        } else {
            p = p->next;                      // 只有不相等时才前进
        }
    }
}

/* 无序单链表去重：两重循环 O(n^2)（想更快就先排序，或者用哈希表 O(n)） */
void UniqueUnordered(Node* first) {
    for (Node* p = first; p; p = p->next) {
        Node* pre = p;
        while (pre->next) {
            if (pre->next->data == p->data) {
                Node* q = pre->next;
                pre->next = q->next;
                delete q;
            } else pre = pre->next;
        }
    }
}

/* 交集：两表均递增有序。时间 O(m+n)，结果按值升序 */
Node* Intersect(Node* a, Node* b) {
    Node dummy; Node* r = &dummy;
    while (a && b) {
        if (a->data == b->data) {             // 相等 ⇒ 是交集元素
            r->next = new Node(a->data);
            r = r->next;
            a = a->next;
            b = b->next;
        } else if (a->data < b->data) {
            a = a->next;                      // a 太小，不可能再出现在交集里
        } else {
            b = b->next;
        }
    }
    r->next = nullptr;
    return dummy.next;
}

/* 并集：两表均递增有序，结果不含重复值。时间 O(m+n) */
Node* Union(Node* a, Node* b) {
    Node dummy; Node* r = &dummy;
    while (a && b) {
        int v;
        if (a->data < b->data)      { v = a->data; a = a->next; }
        else if (a->data > b->data) { v = b->data; b = b->next; }
        else                        { v = a->data; a = a->next; b = b->next; }  // 相等只取一次
        if (!r->next || r->data != v) { r->next = new Node(v); r = r->next; }
    }
    for (Node* p = a ? a : b; p; p = p->next)
        if (r->data != p->data) { r->next = new Node(p->data); r = r->next; }
    r->next = nullptr;
    return dummy.next;
}

Node* Build(const int arr[], int n) {
    Node dummy; Node* r = &dummy;
    for (int i = 0; i < n; ++i) { r->next = new Node(arr[i]); r = r->next; }
    return dummy.next;
}
void Show(const char* tag, Node* p) { cout << tag; for (; p; p = p->next) cout << p->data << " "; cout << endl; }

int main() {
    int d[] = {1, 1, 2, 3, 3, 3, 5};
    Node* L = Build(d, 7);
    UniqueSorted(L);
    Show("去重后 : ", L);                       // 1 2 3 5

    int x[] = {1, 3, 5, 7, 9};
    int y[] = {3, 4, 5, 9, 10};
    Show("交集   : ", Intersect(Build(x, 5), Build(y, 5)));  // 3 5 9
    Show("并集   : ", Union(Build(x, 5), Build(y, 5)));      // 1 3 4 5 7 9 10
    return 0;
}

2.3.13 单链表的优缺点小结

2.4 双向链表：每个结点多存一个「回头路」

单链表最大的不便在删除：明明已经拿到了要删的结点 q， 却还得从头走一遍去找它的前驱，白白花掉 O(n)。 根因是指针是单向的，回头无路。 双向链表 doubly linked list 的解决方案简单粗暴：每个结点再存一个指向前驱的指针。

2.4.1 结点结构与「四条指针」的修改顺序

prior

前驱指针，指向前一个结点；首元结点的 prior 为 NULL（非循环双链表）。

data

数据域。

next

后继指针，指向后一个结点；尾结点的 next 为 NULL。

在 p 之后插入新结点 s，一共要改四条指针。 标准顺序是「先处理新结点自己的两条，再处理邻居的两条」：

为什么 ③ 必须在 ④ 之前？因为 ③ 里要用到 p->next 找到「原来的后继」。 一旦先执行 ④，p->next 就变成 s 了，原来那个后继的 prior 就再也改不到——结果是新结点的前驱链 s->prior = p 成立， 但原后继的 prior 仍然指向 p，双向链在这一点「断了一半」， 反向遍历时会直接跳过 s。这与单链表「先连后断」是同一个道理： 凡是需要用到旧指针值的地方，都必须排在覆盖它的赋值之前。

交互演示把每一步的四条指针拆开，请特别留意第 ③ 步与第 ④ 步的先后：

2.4.2 双向链表完整实现 DLinkList

/* ==========================================================================
   双向链表 —— 每个结点多一个「前驱指针」，插入删除就不用找前驱了
   --------------------------------------------------------------------------
   结点结构：
       struct Node { int val; Node *pre, *nxt; };
                      数据域   前驱     后继

   和单链表比，它多花的代价是「每个结点多一个指针域」；
   换来的是三件事：
       ① 删除某个结点不用先找前驱 —— 直接靠 p->pre 就能拿到，O(1)
       ② 可以反向遍历
       ③ 能在某个结点「前面」插入，也是 O(1)

   竞赛里什么时候用？主要是需要「双向删除」的场景，例如 LRU 缓存、双端队列的实现。
   日常做题用数组模拟双向链表更常见（int pre[N], nxt[N]），速度更快。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *pre, *nxt;                     // 前驱 + 后继
    Node(int v = 0, Node *p = nullptr, Node *n = nullptr) : val(v), pre(p), nxt(n) {}
};

Node *head;                              // 头结点（哑结点）
Node *tail;                              // 尾结点（哑结点），这样两端插入都 O(1)

void InitList() {
    head = new Node();
    tail = new Node();
    head->nxt = tail;                    // 空表：head <-> tail
    tail->pre = head;
}

bool Empty() { return head->nxt == tail; }

/* ---------- 在结点 p 的「后面」插入 x：改四条指针，O(1) ----------
   顺序要点：先把新结点的两个指针接好，再改邻居的指针。
   （先改邻居也不会错，但要保证每一步引用的结点都还有效） */
void InsertAfter(Node *p, int x) {
    Node *q = new Node(x, p, p->nxt);    // 新结点：前驱=p，后继=p 原来的后继
    p->nxt->pre = q;                     // 原来的后继，前驱改成新结点
    p->nxt = q;                          // p 的后继改成新结点
}

/* ---------- 在结点 p 的「前面」插入 x：O(1)（这是双链表独有的便利） ---------- */
void InsertBefore(Node *p, int x) {
    InsertAfter(p->pre, x);              // 在「p 的前驱」后面插入 = 在 p 前面插入
}

/* ---------- 删除结点 p：两条指针，O(1)，不需要找前驱 ---------- */
void Erase(Node *p) {
    p->pre->nxt = p->nxt;
    p->nxt->pre = p->pre;
    delete p;
}

void PushBack(int x) { InsertBefore(tail, x); }    // 插到尾结点前面 = 表尾
void PushFront(int x) { InsertAfter(head, x); }    // 插到头结点后面 = 表头

Node *GetElem(int i) {                   // 按位查找，O(n)
    if (i < 1) return nullptr;
    Node *p = head->nxt;
    for (int j = 1; p != tail && j < i; ++j) p = p->nxt;
    return (p == tail) ? nullptr : p;    // 走到尾结点说明越界
}

void PrintForward(const char *title = "") {
    printf("%s正向：", title);
    for (Node *p = head->nxt; p != tail; p = p->nxt) printf("%d ", p->val);
    printf("\n");
}

void PrintBackward(const char *title = "") {     // 双链表才能这么干
    printf("%s反向：", title);
    for (Node *p = tail->pre; p != head; p = p->pre) printf("%d ", p->val);
    printf("\n");
}

int main() {
    InitList();
    for (int x : {1, 2, 3, 4, 5}) PushBack(x);
    PrintForward("尾插 1..5  ");
    PrintBackward("尾插 1..5  ");        // 顺序是反的：5 4 3 2 1

    PushFront(0);
    PrintForward("头插 0 后  ");          // 0 1 2 3 4 5

    Node *p = GetElem(3);                 // 第 3 个结点（值 2）
    InsertBefore(p, 99);                  // 在它前面插入 —— 单链表做不到 O(1)
    PrintForward("在 2 前面插 99 ");       // 0 1 99 2 3 4 5

    Erase(p);                             // 只给结点指针就删掉它，O(1)
    PrintForward("删掉 2 后  ");          // 0 1 99 3 4 5

    printf("空表吗：%s\n", Empty() ? "是" : "否");

    /* ---------- 与单链表对比（考点） ----------
       维度            单链表          双向链表
       每结点指针域     1 个            2 个
       删除已知结点     O(n)（要找前驱）  O(1)
       在结点前插入     O(n)            O(1)
       反向遍历         不行            可以
       空间开销         小              每结点多 8 字节

       记忆点：双向链表是用「空间」换「删除便利」，典型应用是 LRU 缓存与双端队列。 */
    return 0;
}

2.4.3 方便在哪，代价是什么

2.5 循环链表：把尾巴接回头上

单链表的尾结点 next 是 NULL，走到头就没路了。 如果让尾结点的 next 指回头结点，就得到循环链表 circular linked list。 它最大的价值是：从表中任意一个结点出发，都能遍历到整张表—— 这在「轮流调度」「环形缓冲」这类场景里是刚需。

2.5.1 遍历结束条件：为什么是 p != head 而不是 p != NULL

这是循环链表最核心的一个改动。在普通单链表里，我们靠 while (p != NULL) 判断「走完了」； 但在循环链表里根本不存在 NULL——每个结点的 next 都有指向， 循环条件若还写 p != NULL，程序会永远转下去（死循环）。 正确的结束条件是「回到起点」：

不带头结点时之所以要用 do-while，是因为 p 一开始就等于 first，如果用 while (p != first)，循环体一次都不会执行。 这个小细节是考试里非常爱考的「循环链表遍历」代码填空题。

2.5.2 只设尾指针：一个 O(1) 换两个 O(1)

普通单链表只设头指针时，表头插入是 O(1)，表尾插入是 O(n)（要走到尾）。 循环链表只要把指针设在尾结点上，两个操作就都变成 O(1)：

• 表尾在哪？ 就是 rear 本身，直接可用。
• 表头在哪？ rear->next 是头结点，rear->next->next 就是首元结点，两步常数操作。

所以「在表头插入」和「在表尾插入」都不需要遍历。这个技巧在实现链式队列（第 04 讲）时是标准做法： 队列需要「队尾入队 + 队头出队」，用只设尾指针的循环链表，两个操作都是 O(1)。

/* ==========================================================================
   循环链表 —— 尾结点的 next 指回头结点，整个表连成一个环
   --------------------------------------------------------------------------
   和普通单链表的唯一区别：
       普通单链表走到尾结点时 p->nxt == NULL（这是遍历结束的条件）
       循环链表没有 NULL，遍历结束的条件是「p->nxt == head」（回到起点）

   ⚠️ 高频易错点：把循环链表当普通链表写，判断 p != NULL 会死循环！

   循环链表最实用的一招：**只设尾指针 rear（不设头指针）**
       · 表头结点 = rear->nxt->nxt（跳过哑结点）
       · 在表头插入、在表尾插入都是 O(1)
       普通单链表想在表尾插入必须从头走一遍（O(n)），这是循环链表的优势。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head;                  // 头结点（哑结点），head->nxt 是首元结点

void InitList() {
    head = new Node();
    head->nxt = head;        // 空表：自己指自己，形成只有哑结点的环
}

bool Empty() { return head->nxt == head; }

/* ---------- 尾插：先找到尾结点（p->nxt == head 就是尾），再接到后面 ---------- */
void PushBack(int x) {
    Node *p = head;
    while (p->nxt != head) p = p->nxt;     // 注意终止条件是回到 head，不是 NULL
    Node *q = new Node(x, head);           // 新结点的 next 指向头结点，闭环
    p->nxt = q;
}

/* ---------- 头插：插在首元结点前面，O(1) ---------- */
void PushFront(int x) {
    head->nxt = new Node(x, head->nxt);
}

/* ---------- 遍历：从头结点后面出发，走回 head 就停 ---------- */
void PrintList(const char *title = "") {
    printf("%s：", title);
    if (Empty()) { printf("（空表）\n"); return; }
    for (Node *p = head->nxt; p != head; p = p->nxt) printf("%d -> ", p->val);
    printf("回到头结点\n");
}

int main() {
    InitList();
    printf("刚建好是空表吗：%s\n", Empty() ? "是" : "否");
    PrintList("空表");

    for (int x : {1, 2, 3, 4, 5}) PushBack(x);
    PrintList("尾插 1..5");

    PushFront(0);
    PrintList("头插 0");

    /* ---------- 只设尾指针的版本：两端插入都是 O(1) ---------- */
    puts("\n---- 只设尾指针 rear 的循环链表 ----");
    Node *rear = new Node();          // 只用一个哑结点当尾指针
    rear->nxt = rear;                 // 空表
    auto pushBackFast = [&](int x) {  // 表尾插入 O(1)
        Node *q = new Node(x, rear->nxt);
        rear->nxt = q;
        rear = q;
    };
    auto pushFrontFast = [&](int x) { // 表头插入 O(1)
        Node *first = rear->nxt;      // 首元结点
        rear->nxt = new Node(x, first);
    };
    for (int x = 1; x <= 3; ++x) pushBackFast(x * 10);
    pushFrontFast(5);                 // 插到最前面
    pushBackFast(40);                 // 插到最后面
    printf("从首元结点开始打印：");
    for (Node *p = rear->nxt; ; p = p->nxt) {
        printf("%d ", p->val);
        if (p == rear) break;         // 走到尾指针就停
    }
    printf("\n");

    /* ---------- 结论（考点） ----------
       ① 遍历终止条件：p != head（或回到起点），不是 p != NULL
       ② 只设尾指针时：表头插入 O(1)、表尾插入 O(1)
       ③ 典型应用：约瑟夫环（Josephus）问题——下面 static_list 段之后还有专门一段 */
    return 0;
}

2.5.3 约瑟夫环（Josephus）：循环链表的经典应用

问题描述：n 个人围成一圈，编号 1…n。 从 1 号开始报数，每报到 m 的人出圈，然后从出圈者的下一位重新从 1 报数， 如此反复，求最后剩下的人的编号。

为什么它天然适合循环链表？因为「报数到末尾再从头继续」这件事， 在循环链表里就是 p = p->next 一直走下去—— 不需要任何取模运算或边界判断。用数组模拟的话，每次都要 pos = (pos + 1) % n 并跳过已出圈的人，代码更啰嗦。

// josephus.cpp —— 约瑟夫环：循环链表完整解法
#include <iostream>
using namespace std;

struct Node {
    int   id;                                   // 编号 1..n
    Node* next;
    Node(int i = 0, Node* n = nullptr) : id(i), next(n) {}
};

/* n 个人围成一圈，从 1 号开始报数，报到 m 的人出圈，返回最后剩下的人的编号 */
int Josephus(int n, int m) {
    if (n <= 0 || m <= 0) return -1;

    /* 第一步：建环。先建 1 号，再尾插其余，最后让尾结点指回 1 号 */
    Node* head = new Node(1);
    Node* tail = head;
    for (int i = 2; i <= n; ++i) {
        tail->next = new Node(i);
        tail = tail->next;
    }
    tail->next = head;                          // 首尾相接，成环（这一步不能漏）

    /* 第二步：反复报数 + 摘链 */
    Node* pre = tail;                           // pre 始终是 p 的前驱
    Node* p   = head;                           // 从 1 号开始报「1」
    cout << "出圈顺序: ";
    while (p->next != p) {                      // 只剩一个结点时，p->next 指向自己
        for (int k = 1; k < m; ++k) {           // 报数到 m：走 m-1 步
            pre = p;
            p = p->next;
        }
        cout << p->id << " ";
        pre->next = p->next;                     // 摘链：前驱跨过 p
        Node* dead = p;
        p = p->next;                            // 从下一位重新从 1 开始报数
        delete dead;                            // 释放出圈者，防止内存泄漏
    }
    cout << endl;

    int survivor = p->id;
    delete p;                                   // 最后一个结点也要释放
    return survivor;
}

/* 对照：数学递推解法（O(n) 时间、O(1) 空间），第 13 讲会详细推导 */
int JosephusMath(int n, int m) {
    int f = 0;                                  // f(1) = 0（0-based）
    for (int i = 2; i <= n; ++i) f = (f + m) % i;
    return f + 1;                               // 转回 1-based
}

int main() {
    cout << "n=8, m=3 => 幸存者 " << Josephus(8, 3) << endl;         // 7
    cout << "n=41, m=3 => 幸存者 " << Josephus(41, 3) << endl;       // 31（经典约瑟夫斯问题）
    cout << "数学法校验 n=8, m=3 => " << JosephusMath(8, 3) << endl;   // 7
    cout << "数学法校验 n=41, m=3 => " << JosephusMath(41, 3) << endl; // 31
    return 0;
}

2.5.4 循环双链表：删除任意结点的终极形态

把「循环」和「双向」合起来，就得到循环双链表 circular doubly linked list： 头结点的 prior 指向尾结点，尾结点的 next 指向头结点， 整条链上一个 NULL 都没有。

这个「没有 NULL」的性质带来一个非常漂亮的结论： 删除任意给定结点 p 只需要两行，而且完全不需要判空：

对比一下：普通双链表要写 if (q->next) q->next->prior = ...， 单链表还要先 O(n) 找前驱。循环双链表把这两种特判和额外开销全部消掉了， 代价仅仅是「头结点的两个指针都要正确初始化」。这也是为什么 STL 的 std::list 底层就是一个带哨兵结点的循环双链表。

/* ==========================================================================
   循环双链表 —— 环形 + 双向，插入删除最"对称"的结构
   --------------------------------------------------------------------------
   结点：struct Node { int val; Node *pre, *nxt; };
   空表状态：head->nxt = head->pre = head（自己指自己）

   它的好处是：不需要头结点/尾结点两个哑结点，一个 head 就能两端操作，
   插入删除的指针修改是对称的：
       在 p 后面插入 q： q->nxt = p->nxt; q->pre = p;
                        p->nxt->pre = q;  p->nxt = q;
       删除 p：        p->pre->nxt = p->nxt;  p->nxt->pre = p->pre;
   （只有环形的结构里，p->pre 永远存在，不需要判空指针，代码最干净。）
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *pre, *nxt;
    Node(int v = 0) : val(v), pre(this), nxt(this) {}   // 自己指自己 = 只有一个元素的环
};

Node *head;

void InitList() {
    head = new Node();               // 头结点自己成环
}

bool Empty() { return head->nxt == head; }

/* ---------- 把 q 接在 p 的后面（q 必须是一个「孤立」结点） ---------- */
void Link(Node *p, Node *q) {
    q->nxt = p->nxt;
    q->pre = p;
    p->nxt->pre = q;
    p->nxt = q;
}

/* ---------- 从环里摘掉 p ---------- */
void Unlink(Node *p) {
    p->pre->nxt = p->nxt;
    p->nxt->pre = p->pre;
    p->nxt = p->pre = p;             // 让它自己成环，避免野指针
}

void PushBack(int x)  { Link(head->pre, new Node(x)); }   // 接在尾结点后面
void PushFront(int x) { Link(head, new Node(x)); }        // 接在头结点后面

int Length() {
    int n = 0;
    for (Node *p = head->nxt; p != head; p = p->nxt) ++n;
    return n;
}

Node *GetElem(int i) {
    if (i < 1) return nullptr;
    Node *p = head->nxt;
    for (int j = 1; p != head && j < i; ++j) p = p->nxt;
    return (p == head) ? nullptr : p;
}

void PrintForward(const char *title = "") {
    printf("%s正向：", title);
    for (Node *p = head->nxt; p != head; p = p->nxt) printf("%d ", p->val);
    printf("\n");
}
void PrintBackward(const char *title = "") {
    printf("%s反向：", title);
    for (Node *p = head->pre; p != head; p = p->pre) printf("%d ", p->val);
    printf("\n");
}

int main() {
    InitList();
    printf("空表吗：%s，长度 %d\n", Empty() ? "是" : "否", Length());   // 是，0

    for (int x : {1, 2, 3}) PushBack(x);
    for (int x : {0, -1}) PushFront(x);
    PrintForward("插入后 ");        // -1 0 1 2 3
    PrintBackward("插入后 ");       // 3 2 1 0 -1
    printf("长度 = %d\n", Length()); // 5

    /* 删掉中间那个结点：只给指针，O(1) */
    Node *p = GetElem(3);           // 值 1
    Unlink(p);
    PrintForward("删掉 1 后 ");      // -1 0 2 3

    /* 在它前面插一个（利用 p->pre，不需要找前驱） */
    Link(GetElem(2)->pre, new Node(88));   // 在 0 前面插 88
    PrintForward("0 前面插 88 ");    // -1 88 0 2 3
    PrintBackward("反向看   ");      // 3 2 0 88 -1

    /* ---------- 对比小结 ----------
       循环链表：尾结点的 next 回头结点 → 遍历判据是回到起点
       双向链表：多了 pre 指针 → 删除/前插 O(1)
       循环双链表：两者结合 → 类里最"对称"、判空指针最少，但每个结点两个指针域

       竞赛实战：需要频繁在两端增删时，优先用 std::list（它就是循环双链表）
       或直接用数组模拟，比手写指针更不容易出错。 */
    return 0;
}

2.6 静态链表：用数组模拟指针

在早期语言（如 BASIC、FORTRAN）里根本没有指针， 但人们又需要链表「插入删除不搬家」的好处，于是发明了静态链表 static linked list： 用一整块数组存放结点，用数组下标代替指针。 这个「代替指针的下标」有一个专门的名字——游标 cursor。

约定：next == -1 表示空指针 NULL（有些教材用 0， 但那样下标 0 就不能用了）。由于每个结点的「地址」就是它在数组里的下标， 我们永远不需要真的取地址，只需要在下标之间跳来跳去。

静态链表的插入删除代码与单链表几乎一模一样，只是把 p = p->next 换成 p = a[p].next， 把 new Node(e) 换成 Malloc()（从备用链表摘一个下标）， 把 delete q 换成 Free(q)（还回备用链表）。

// static_list.cpp —— 静态链表：数组 + 游标，完整实现插入 / 删除 / 遍历
#include <iostream>
using namespace std;

const int MAXN = 100;

struct SNode {
    int data;
    int next;                  // 游标：下一个结点在数组中的下标，-1 表示 NULL
};

SNode a[MAXN];
const int FREE_HEAD = 0;       // a[0] 作为「备用链表」的头结点（相当于内存分配器）
const int HEAD      = 1;       // a[1] 作为「数据链表」的头结点（哨兵）

void InitList() {
    for (int i = 0; i < MAXN - 1; ++i) a[i].next = i + 1;
    a[MAXN - 1].next = -1;     // 先把所有结点串成一条备用链表
    a[HEAD].next      = -1;    // 数据链表为空
    a[FREE_HEAD].next = 2;     // 下标 0、1 已被占用，备用链表从 2 开始
}

int Malloc() {                 // 从备用链表借一个结点，返回下标；-1 表示空间耗尽
    int i = a[FREE_HEAD].next;
    if (i != -1) a[FREE_HEAD].next = a[i].next;
    return i;                  // 这一步相当于 new 失败时返回空
}

void Free(int k) {             // 把下标 k 的结点还给备用链表（相当于 delete）
    a[k].next = a[FREE_HEAD].next;
    a[FREE_HEAD].next = k;
}

int Length() {
    int n = 0;
    for (int p = a[HEAD].next; p != -1; p = a[p].next) ++n;   // 注意：-1 才是终止条件
    return n;
}

bool ListInsert(int i, int e) {                 // 在位序 i 插入
    if (i < 1 || i > Length() + 1) return false;
    int p = HEAD;                               // p 是「下标」，不是指针
    for (int k = 1; k < i; ++k) p = a[p].next;  // 走到第 i-1 个结点
    int s = Malloc();
    if (s == -1) return false;                  // 空间满，相当于 new 失败
    a[s].data = e;
    a[s].next = a[p].next;                      // ① 先连
    a[p].next = s;                              // ② 后断——和单链表完全一样的套路
    return true;
}

bool ListDelete(int i, int& e) {                // 删除位序 i
    if (i < 1 || i > Length()) return false;
    int p = HEAD;
    for (int k = 1; k < i; ++k) p = a[p].next;  // 找前驱
    int q = a[p].next;
    e = a[q].data;
    a[p].next = a[q].next;                      // 跨过 q
    Free(q);                                    // 把下标还回备用链表
    return true;
}

void PrintList() {
    cout << "head";
    for (int p = a[HEAD].next; p != -1; p = a[p].next)
        cout << " -> [" << p << "]" << a[p].data;
    cout << " -> -1　(len=" << Length() << ")" << endl;
}

int main() {
    InitList();
    int arr[] = {21, 32, 45, 58};
    for (int k = 0; k < 4; ++k) ListInsert(Length() + 1, arr[k]);   // 依次追加
    PrintList();                       // head -> [2]21 -> [3]32 -> [4]45 -> [5]58 -> -1

    ListInsert(2, 7);                  // 在下标不连续的情况下「插队」
    PrintList();

    int del = 0;
    ListDelete(3, del);
    cout << "删除了 " << del << endl;
    PrintList();
    /* 关键观察：整张表始终在同一个数组里，插入删除只改游标，没有任何元素搬家。 */
    return 0;
}

2.7 五者对比：一张表看清所有取舍

学到这里，我们已经见了五种线性表的实现。它们解决的是同一个逻辑问题， 差别全部集中在「怎么在内存里表示『下一个』」这一个决定上。 下面这张表请务必自己默写一遍——它是本章的「总账」。

2.7.1 横向对比大表

2.7.2 顺序表 vs 链表：复杂度总表

2.8 选型决策：这道题到底该用顺序表还是链表？

工程中选错存储结构，往往比写错一个循环更致命——因为它决定了整个系统的性能上限。 下面这张流程图把常见判断浓缩成三个问题，从上往下走一遍，基本就能定下来。

2.9 C++ 实战与七条高频易错点

链表代码写不对，往往不是算法想不明白，而是踩了 C++ 内存管理的坑。 下面这七条，每一条都能让你的程序在「本地跑得好好的，一交上去就 RE」。

这七条是「写对」的底线。下一节（2.10）我们换个视角：把这些结构放回真实的操作系统、 数据库与缓存系统里，看工程上究竟在什么条件下选顺序表、什么条件下选链表。

2.10 工程视角：顺序表与链表在真实系统里怎么选

本章的五种结构讲完了。但你心里可能一直有个疑问： 这些课本上的结构，真的会在操作系统、数据库、网络系统里出现吗？ 答案是：不但会出现，而且天天出现。这一节我们离开考卷，去看四个真实的工程现场—— CPU 缓存、动态数组扩容、内核的链表、数据库的主键索引，看看「用连续内存还是用指针串」 这个选择在真实系统里是怎样反复做出的。你会发现，工程师给出的答案和课本上的复杂度表 并不总是吻合，因为真实世界里还有一条课本不写的成本：访存。

2.10.1 先看一个反常识的实验：复杂度相同的两种表，速度差 5～10 倍

取一个再普通不过的任务：求 1 + 2 + 3 + … + n 的和。 分别用顺序表和链表存下 1..n，各写一个循环把它们累加起来。 两个循环都是从头到尾扫一遍、每个元素做一次加法，时间复杂度都是 O(n)， 按课本的分析应该「一样快」。可实测下来通常是这样：

同样的 O(n)，为什么差了 5～10 倍？因为瓶颈不在加法的次数上，而在内存跟不跟得上。

合起来看，实验结果的解释就很直白了：

• 顺序表：读 data[0] 触发一次 cache line 填充， 顺带把 data[0..15] 共 16 个元素全搬进缓存，接下来 15 次全部命中， 每 16 个元素才付一次访存的钱。
• 链表：p = p->next 的地址要等本次访存返回才知道， 于是每个结点几乎都是一次 cache miss：L1 命中约 4 个时钟周期， 内存访问要 200 个上下，差两个数量级。

所以，理论复杂度相同 ≠ 实际性能相同。大 O 只管「操作次数随 n 的增长趋势」， 刻意忽略常数因子，而常数因子里恰好藏着 cache line 与预取器这种数量级的差异。 这也是为什么在竞赛里，理论最优的链表常被数组模拟的版本按在地上摩擦—— 第 08 讲用数组模拟链表（链式前向星）、第 11 讲把堆存进数组（堆排序）， 讲的都是同一件事：能连续，就不要散着放。

2.10.2 动态数组为什么敢「容量翻倍」：均摊 O(1) 的来历

第 2.2 节我们写过动态顺序表的 grow()，也提到 std::vector 是同一套做法， 但留了一个问题没答：容量不够时，为什么是「翻倍」，而不是每次只多开一个？

std::vector 的 push_back 承诺「末尾插入 O(1)」， 可它明明会在某一刻做一件昂贵的事：申请一块更大的内存，把已有的 size 个元素逐个搬过去，再释放旧内存。既然有这次「搬家」，凭什么说它是 O(1)？ 答案在「均摊」二字，而均摊的结论取决于增长策略：

把 O(n) 的总代价摊到 n 次插入上，每次插入平均只花 O(1)。 这就是「均摊 O(1)（amortized O(1)）」：不是每一次都快， 而是连续做任意多次，平均下来每次是常数。单看触发扩容的那一次代价确实是 O(n)， 但你已经「攒」了 n/2 次便宜的插入，早就把账付清了。它与「平均 O(1)」不是一回事： 均摊分析不给概率留位置，它是对任意一串操作序列都成立的最坏保证。

代价也有，必须在工程里认账：

• 浪费空间：size 刚过容量一半时，接近一半内存是闲置的。
• 扩容尖峰：一次申请两块内存（旧块还没释放），对延迟敏感的程序是抖动来源。
• 指针与迭代器全部失效：搬家后元素换了地址，之前存的 &v[i]、迭代器、裸指针统统成了野指针，这是 C++ 最常见的隐性 bug 之一。
• 搬大对象很贵：元素越大，一次扩容的拷贝成本越高。

2.10.3 操作系统（一）：进程就绪队列与空闲内存块链表，为什么内核偏爱链表

场景一：进程就绪队列（ready queue）。 时间片用完的进程要扔到队尾，被唤醒的进程要插到队首或按优先级插到中间， 阻塞、退出时又要从队列中间摘掉。系统里可能同时有几万个就绪任务， CPU 每秒要做几十万次插入和摘除。课本上说「就绪队列是队列」， 但在内核实现里它就是一条链表（Linux 的 CFS 调度器改用红黑树， 任务仍靠链表结点串起来）。

场景二：空闲内存块链表（free list）。 内存管理器要维护「哪些内存块空闲」的账：进程申请时从表里摘一块，释放时把块还回表里。 关键词是插入删除极其频繁、发生在任意位置，而内核从不需要按下标的随机访问。

这两条需求正好踩在链表的甜点区上。但真正让内核不能用顺序表的，是下面这条：

代价也要说清：链表结点逐个分配，每个结点至少多存一个指针（64 位系统上 8 字节）， 内存开销按结点数线性增长，缓存友好度又差（就是上一节讲的指针追逐）。 所以现代内核在能改数组的地方尽量改数组，只有「频繁中间增删 + 地址不能动」时才用链表。

2.10.4 操作系统（二）：LRU 页面置换与缓存淘汰，为什么是「哈希表 + 双向链表」

再看操作系统里的另一个经典问题：内存装不下所有页面，该把哪一页换出去？ 最常用的策略是 LRU（Least Recently Used，最近最少使用）： 淘汰「最久没有被访问过」的那一页。要让这个策略跑起来，数据结构必须同时支持三件事：

1. 给定一个页号，O(1) 判断它在不在内存里（每次访存都要查，慢了整个系统都慢）；
2. 刚被访问过的页面要标记成「最近使用」，也就是移到「最新」那一端；
3. 淘汰时，O(1) 找到并摘掉「最旧」那一端的结点。

三条要求一摆出来，答案已经呼之欲出：

• 第 1 条（按值查找）：顺序表按下标是 O(1)，可我们要按「页号」找， 只能线性扫描 O(n)，链表同样是 O(n)。能 O(1) 定位的只有一种东西： 哈希表（第 10 讲的主角）。
• 第 2、3 条（挪到表头 / 摘掉表尾）：哈希表本身不维护顺序，做不了， 需要一条能 O(1) 摘除任意结点、O(1) 头插的链——双向链表。

于是工程上的标准答案是：哈希表 + 双向链表。哈希表负责「O(1) 定位结点」， 双向链表负责「O(1) 调整顺序」，一句话说清分工就是哈希表管定位，链表管顺序。 这个组合可以原样搬到应用层：Redis 的键淘汰、MySQL 的 Buffer Pool、浏览器缓存淘汰， 用的都是它。

那么这里的链表为什么必须是双向的？回想 2.4 节的结论： 「删除」这个操作本身，需要的是前驱结点。 单链表里拿到 p 之后想删掉它，只能从头再走一遍去找前驱，代价 O(n)； 而双向链表的结点里存着 prior，知道 p 就能立刻写出 p->prior->next = p->next; p->next->prior = p->prior;， 两次赋值、O(1) 完成。

代价也很清楚：每个结点多一个指针域，64 位系统上一个结点从 16 字节涨到 24 字节， 内存多占 50%，哈希表本身还要再占一份空间。所以 LRU 只用在「值得为它多花内存」 的地方——页表、数据库缓冲池这种容量可控、命中率收益极高的场景； 小对象缓存往往退化成近似算法（只记一个访问位、或用 Redis 的随机近似淘汰），用精度换开销。

// lru_list.cpp —— LRU 缓存的最小实现：std::list（双向链表）+ 哈希表
// 说明：std::list 就是本章 2.4 节双向链表的标准库实现，
//       它的 erase(it) 只改两个指针、O(1) 完成，splice 也只是搬动结点、不搬数据。
#include <iostream>
#include <list>
#include <unordered_map>
#include <iterator>
using namespace std;

struct LRUCache {
    struct Entry {
        int key;
        int value;
    };
    int cap;
    std::list<Entry> order;                          // 表头 = 最近使用，表尾 = 最久未用
    std::unordered_map<int, std::list<Entry>::iterator> pos;   // 键 -> 结点在链表中的位置

    LRUCache(int c) : cap(c) {}

    // 访问：命中则把结点挪到表头，并返回值；未命中返回 -1
    int get(int key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;                       // 哈希表 O(1) 判断存在
        std::list<Entry>::iterator p = it->second;
        order.splice(order.begin(), order, p);                // O(1) 摘下来再挂到表头，不拷贝数据
        return p->value;
    }

    // 写入：已存在则改值并挪到表头；不存在则新建，必要时淘汰表尾
    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            std::list<Entry>::iterator p = it->second;
            p->value = value;
            order.splice(order.begin(), order, p);
            return;
        }
        if ((int)order.size() == cap) {                       // 满了：淘汰表尾（最久未使用）
            int oldKey = order.back().key;                    // 先记下键，再去哈希表里删
            pos.erase(oldKey);
            order.pop_back();
        }
        order.push_front(Entry{key, value});                  // 新结点挂表头
        pos[key] = order.begin();                             // 记下它的迭代器，供将来 O(1) 摘除
    }

    int size() { return (int)order.size(); }
};

int main() {
    LRUCache cache(2);                       // 容量 2
    cache.put(1, 10);
    cache.put(2, 20);
    cout << cache.get(1) << endl;            // 10，且 1 变成最近使用
    cache.put(3, 30);                        // 容量满，淘汰最久未用的 2
    cout << cache.get(2) << endl;            // -1，已被淘汰
    cout << cache.get(1) << endl;            // 10，仍在
    cout << cache.get(3) << endl;            // 30
    cout << "size = " << cache.size() << endl;   // size = 2
    return 0;
}
/* 实测输出：10 / -1 / 10 / 30 / size = 2
   复杂度：get 与 put 都是 O(1)。
     - 哈希表负责「按 key 找结点」；
     - 双向链表负责「把结点挪到表头 / 从表尾摘掉」，都是 O(1)。
   若换成单链表：删除已知结点要先找前驱，退化成 O(n)，LRU 也就不成立了。 */

2.10.5 数据库：主键索引为什么是 B+ 树，而不是顺序表或链表

最后一个现场是数据库：一亿条用户记录，按主键 id 建索引， 要求支持 WHERE id = 12345678（等值查找） 和 WHERE id BETWEEN a AND b（范围查找）。 先看课本上的两种结构能不能扛：

这两个结构失败的原因恰好互补：顺序表的问题是「插入要搬家」， 链表的问题是「查找要一步一步走」。而数据库要求既能快速定位， 又能原地增删，还能顺序扫描一个区间。把这三条同时满足的结构， 就是把「多路分支」和「结点内有序数组」叠起来的树——B+ 树。

• 每个结点是一小块有序数组：结点内部用二分定位， 相当于把「顺序表查找快」的优点保留了下来；
• 结点之间用指针分成 m 路：树高只有 logm n， 一亿条数据、m 取几百时树高通常只有 3～4 层，查一条记录只要 3～4 次磁盘 I/O；
• 结点内的插入只影响本结点：跨结点时靠分裂 / 合并局部调整， 不必把整棵树搬一遍——这就避开了顺序表的搬移代价；
• 数据全在叶子层、叶子之间用链表串起来：范围查找定位到起点后顺着叶子链表往后扫即可。 这里又用回了链表，而且只需「顺序往后走」，单链表就够了。

2.10.6 一张表：三个结构在真实工程维度上的对比

把上面四个现场收拢成一张表。注意这里的维度不是考试用的「时间复杂度」， 而是工程上真正要权衡的东西：

和 2.7 节那张结构对比表相比，这里多出来的其实只有两行：「内存开销」与「缓存友好度」。 而恰恰是这两行，解释了为什么「链表的教科书优势」在真实机器上经常缩水： 理论复杂度只算了操作次数，没算每次操作背后的访存代价，而在内存远慢于 CPU 的今天， 后者的权重往往更大。

最后回到一句话：本章讲的所有取舍，在工程里都会以同一种形式出现—— 「我需不需要按下标随机访问？需不需要频繁在中间增删？元素地址会不会被别处引用着？」 把这三个问题问清楚，选型基本就不会错。这也是第 15 讲综合复习时会再拿出来对照的一把尺子。

2.11 本章小结

本章的骨架其实只有一句话：逻辑结构相同，物理实现不同，复杂度就不同。 线性表的逻辑是「一对一」，而「一对一」可以用连续内存的位置相邻来表示， 也可以用散落结点的指针指向来表示。前者叫顺序表，后者叫链表。 后续所有的展开——双向、循环、静态——都只是在这两个极端之间做加法和折中。

2.11.1 一张图记住五种结构

2.11.2 必须能默写出来的六段代码

1. 顺序表插入：边界 len+1、满了先 grow()、从后往前搬元素。
2. 顺序表删除：边界 len、先用引用带回被删值、从前往后搬元素。
3. 单链表插入：走 i−1 步找前驱、s->next = p->next; 在前。
4. 单链表删除：先 q = p->next; 保存、再跨过、最后 delete q;。
5. 反转链表（迭代）：pre/cur/nxt 三指针，四步一轮。
6. Floyd 判环 + 找入口：快慢指针相遇；两指针分别从表头与相遇点同步走。

2.12 考点归纳与自测

2.12.1 自测题（答案已折叠，请先自己做）

// delete_all_x.cpp —— 删除单链表中所有值为 x 的结点（一趟扫描，O(n) 时间 / O(1) 空间）
#include <iostream>
using namespace std;

struct Node {
    int   data;
    Node* next;
    Node(int d = 0, Node* n = nullptr) : data(d), next(n) {}
};

void DeleteAllX(Node* head, int x) {   // head 是头结点
    Node* p = head;                    // p 是「最后一个确定保留的结点」
    while (p->next) {
        if (p->next->data == x) {
            Node* q = p->next;         // 保存待删结点
            p->next = q->next;         // 跨过它
            delete q;                  // 释放
            /* 注意：这里 p 不前进！新后继可能仍是 x */
        } else {
            p = p->next;               // 只有确认保留才前进
        }
    }
}
/* 三种情况都被覆盖：
   - 连续多个 x：删掉一个后 p 不动，下一轮继续检查新的 p->next；
   - x 在表尾：p->next 是尾结点，删除后 p->next 变成 nullptr，循环正常结束；
   - 全是 x：p 始终停在头结点，把所有数据结点依次删光，最后 p->next == nullptr。 */

/* 测试：1 2 2 2 3 4 2 —— 同时覆盖「连续多个 x」「x 在表尾」两种情况 */
int main() {
    Node* head = new Node();               // 头结点（哑结点）
    Node* r = head;
    int a[] = {1, 2, 2, 2, 3, 4, 2};
    for (int k = 0; k < 7; ++k) { r->next = new Node(a[k]); r = r->next; }

    DeleteAllX(head, 2);

    for (Node* p = head->next; p; p = p->next) cout << p->data << " ";
    cout << endl;                          // 1 3 4

    for (Node* p = head; p; ) { Node* q = p->next; delete p; p = q; }  // 整表释放
    return 0;
}