第3章 链表

---

🎯 本章学习目标

通过本章的学习，你将能够：

1. 理解链表概念：清楚链表与数组的区别，知道各自的优缺点
2. 掌握单链表：熟练掌握单链表的创建、插入、删除、遍历、查找操作
3. 实现链表反转：能用三指针法反转单链表，理解每步指针变化
4. 掌握双链表：理解双链表的前驱后继指针，会进行插入删除操作
5. 理解循环链表：掌握循环链表的结构特点和遍历终止条件
6. 解决约瑟夫问题：能用循环链表模拟约瑟夫问题的出列过程
7. 分析时间复杂度：能分析链表各种操作的时间复杂度
8. 处理边界情况：注意空链表、只有一个节点、头尾节点等特殊情况
9. 读懂链表代码：能快速分析链表操作代码的执行结果
10. 应对代码填空：熟练掌握链表反转、插入删除等经典代码填空

---

🗺️ 本章知识图谱

链表
├── 基础概念
│   ├── 链表 vs 数组
│   │   ├── 数组：连续内存、随机访问O(1)、插入删除O(n)
│   │   └── 链表：离散内存、随机访问O(n)、插入删除O(1)（已知位置）
│   └── 节点结构（数据域 + 指针域）
├── 单链表
│   ├── 节点定义（struct + next指针）
│   ├── 创建（头插法 / 尾插法）
│   ├── 遍历（while(p!=nullptr)）
│   ├── 查找
│   ├── 插入
│   │   ├── 头插（新节点next=head; head=新节点）
│   │   ├── 尾插（找到尾节点，next=新节点）
│   │   └── 中间插（先找前驱，改两个指针）
│   ├── 删除
│   │   ├── 按值删除
│   │   └── 按位置删除
│   └── 反转（三指针法：prev/curr/nextTemp）
├── 双链表
│   ├── 节点定义（prev + val + next）
│   ├── 双向遍历
│   ├── 插入（改四个指针）
│   └── 删除（改两个指针）
├── 循环链表
│   ├── 单循环链表（尾节点next=头节点）
│   ├── 遍历终止条件（回到头节点）
│   └── 约瑟夫问题
└── 经典问题
    ├── 链表反转
    ├── 约瑟夫环
    ├── 合并有序链表
    └── 快慢指针找中点

---

一、为什么需要链表？

数组的特点是内存连续、随机访问快（O(1)），但在中间插入/删除元素需要挪动大量数据（O(n)），且大小固定。链表通过指针串联节点，实现了 O(1) 的插入删除（已知位置时），代价是无法随机访问。

数组：  [10] [20] [30] [40]    ← 连续内存，下标随机访问
链表：  [10|•]→[20|•]→[30|•]→[40|∅]  ← 离散内存，指针串联

---

二、单链表

2.1 节点定义

struct ListNode {
    int val;               // 数据域
    ListNode* next;        // 指针域，指向下一个节点
    ListNode(int x) : val(x), next(nullptr) {}
};

2.2 创建与遍历

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int main() {
    // 依次创建节点 1 -> 2 -> 3
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);

    // 遍历链表
    ListNode* p = head;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    // 输出：1 2 3
    return 0;
}

⚠️ 易错点：遍历条件是 p != nullptr，不是 p->next != nullptr。后者会漏掉最后一个节点！

2.3 插入操作

① 头插法（在链表头部插入）

// 在头部插入值为 x 的新节点
ListNode* insertHead(ListNode* head, int x) {
    ListNode* node = new ListNode(x);
    node->next = head;   // 新节点指向原头节点
    return node;         // 新节点成为新的头节点
}

② 尾插法（在链表尾部插入）

// 在尾部插入值为 x 的新节点
ListNode* insertTail(ListNode* head, int x) {
    ListNode* node = new ListNode(x);
    if (head == nullptr) return node;  // 空链表直接返回新节点
    ListNode* p = head;
    while (p->next != nullptr) {       // 找到最后一个节点
        p = p->next;
    }
    p->next = node;
    return head;
}

③ 中间插入（在指定节点后插入）

// 在节点 pos 之后插入值为 x 的新节点
void insertAfter(ListNode* pos, int x) {
    if (pos == nullptr) return;
    ListNode* node = new ListNode(x);
    node->next = pos->next;  // 新节点指向 pos 的后继
    pos->next = node;        // pos 指向新节点
}

🎯 记忆口诀：插入操作"先连后断"——新节点先指向后继，再让前驱指向新节点。顺序写反会丢失后继链表！

2.4 删除操作

// 删除链表中第一个值为 x 的节点
ListNode* deleteNode(ListNode* head, int x) {
    if (head == nullptr) return nullptr;
    // 单独处理头节点
    if (head->val == x) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    // 查找待删节点的前驱
    ListNode* p = head;
    while (p->next != nullptr && p->next->val != x) {
        p = p->next;
    }
    if (p->next != nullptr) {
        ListNode* temp = p->next;
        p->next = temp->next;  // 前驱跳过待删节点
        delete temp;
    }
    return head;
}

⚠️ 易错点：删除节点后必须 delete 释放内存，否则造成内存泄漏。考试中如果使用完整个链表，也应遍历释放所有节点。

2.5 查找操作

// 查找值为 x 的节点，找到返回指针，否则返回 nullptr
ListNode* search(ListNode* head, int x) {
    ListNode* p = head;
    while (p != nullptr) {
        if (p->val == x) return p;
        p = p->next;
    }
    return nullptr;
}

2.6 反转链表 ⭐

反转是单链表最高频的考点，必须滚瓜烂熟！

迭代法（三指针）：

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;   // 前驱节点
    ListNode* curr = head;      // 当前节点
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;  // 暂存后继
        curr->next = prev;                // 反转指针
        prev = curr;                      // prev 前进
        curr = nextTemp;                  // curr 前进
    }
    return prev;  // prev 成为新的头节点
}

反转过程图示：

初始：  ∅ ←prev  [1]→[2]→[3]→∅
              curr

第1步： ∅ ←[1] ←prev  [2]→[3]→∅
                   curr

第2步： ∅ ←[1]←[2] ←prev  [3]→∅
                        curr

第3步： ∅ ←[1]←[2]←[3] ←prev  ∅
                             curr (结束)

🎯 考试常见考法：程序阅读题给出反转代码，问输出结果。或者代码填空题挖空 curr->next = prev 等关键语句。

---

三、双链表

单链表只能"往后走"，双链表的每个节点同时持有 prev 和 next 两个指针，可以双向遍历。

3.1 节点定义

struct DListNode {
    int val;
    DListNode* prev;   // 指向前驱
    DListNode* next;   // 指向后继
    DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

3.2 双向遍历

// 正向遍历
DListNode* p = head;
while (p != nullptr) {
    cout << p->val << " ";
    p = p->next;
}

// 反向遍历（需要先找到尾节点，或维护 tail 指针）
DListNode* q = tail;
while (q != nullptr) {
    cout << q->val << " ";
    q = q->prev;
}

3.3 插入操作（在节点 pos 之后插入）

void insertAfter(DListNode* pos, int x) {
    if (pos == nullptr) return;
    DListNode* node = new DListNode(x);
    node->prev = pos;
    node->next = pos->next;
    if (pos->next != nullptr) {
        pos->next->prev = node;
    }
    pos->next = node;
}

3.4 删除操作

void deleteNode(DListNode* node) {
    if (node == nullptr) return;
    if (node->prev != nullptr) {
        node->prev->next = node->next;
    }
    if (node->next != nullptr) {
        node->next->prev = node->prev;
    }
    delete node;
}

⚠️ 易错点：双链表插入/删除需要同时修改 4 个指针方向（新节点的 prev/next + 前后节点的指针），漏改任何一个都会断链。

---

四、循环链表

循环链表的尾节点指向头节点（而非 nullptr），形成一个环。

单链表：  head→[1]→[2]→[3]→∅
循环链表：head→[1]→[2]→[3]→┐
           ↑──────────────┘

4.1 遍历循环链表

// 遍历循环链表（注意终止条件与单链表不同！）
void traverse(DListNode* head) {
    if (head == nullptr) return;
    DListNode* p = head;
    do {
        cout << p->val << " ";
        p = p->next;
    } while (p != head);  // 回到头节点时停止
}

⚠️ 易错点：循环链表不能用 while (p != nullptr) 作为终止条件，否则死循环！必须用 do-while 或判断 p == head。

4.2 经典应用：约瑟夫问题 ⭐

n 个人围成一圈，从第 1 个人开始报数，数到 m 的人出列，求最后剩下的人。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // 构建循环链表
    struct Node {
        int id;
        Node* next;
        Node(int x) : id(x), next(nullptr) {}
    };

    Node* head = new Node(1);
    Node* p = head;
    for (int i = 2; i <= n; i++) {
        p->next = new Node(i);
        p = p->next;
    }
    p->next = head;  // 首尾相连，形成环

    // 模拟报数
    Node* prev = p;  // prev 初始指向最后一个节点（head 的前驱）
    p = head;
    while (p->next != p) {  // 只剩一个节点时停止
        // 报数 m-1 次，让 p 指向待删节点，prev 指向其前驱
        for (int i = 1; i < m; i++) {
            prev = p;
            p = p->next;
        }
        // 删除 p 指向的节点
        cout << p->id << " ";
        prev->next = p->next;
        Node* temp = p;
        p = p->next;
        delete temp;
    }
    cout << p->id << endl;  // 最后幸存者
    return 0;
}

输入 5 3，输出：3 1 5 2 4（出列顺序），最后幸存者为 4。

---

五、三种链表对比

特性	单链表	双链表	循环链表
指针方向	仅 next	prev + next	next（首尾相连）
遍历方向	只能从前向后	可双向遍历	可从任意节点循环遍历
插入/删除（已知节点）	O(1)，但需找前驱 O(n)	O(1)，无需找前驱	同单链表
查找前驱	需从头遍历 O(n)	直接 prev，O(1)	需遍历 O(n)
内存开销	1个指针/节点	2个指针/节点	1个指针/节点
适用场景	栈、哈希链、简单序列	LRU缓存、需要双向操作	约瑟夫问题、轮询调度
判断表尾	next == nullptr	next == nullptr	next == head

🎯 GESP 考法提示：链表部分以程序阅读题和代码填空题为主，重点考查指针操作顺序、遍历终止条件、反转和约瑟夫问题。手写代码题则可能要求实现完整的增删查改。

---

六、📝 实战练习

练习题 1（填空题）

题目： 给定一个单链表，头节点为 head，以下代码的功能是反转链表。请在空白处填写正确的语句。

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;
        _______________;  // ①
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

🔑 点击查看答案与解析

答案： ① 处填 curr->next = prev

解析： 反转的核心就是让当前节点的 next 指向前驱节点 prev。三指针各司其职：nextTemp 暂存后继防止断链，curr->next = prev 完成反转，然后两个指针各进一步。这道题是 GESP 高频代码填空题，务必牢记。

---

练习题 2（单选题）

题目： n=7 个人围成一圈，从第 1 个人开始报数，每次数到 3 的人出列。下列哪个是正确的出列顺序？

A. 3, 6, 2, 7, 5, 1, 4 B. 3, 6, 1, 5, 2, 7, 4 C. 3, 6, 2, 7, 1, 5, 4 D. 3, 6, 1, 7, 2, 5, 4

🔑 点击查看答案与解析

答案： A

解析： 手动模拟：

• 第1轮：1,2,3 → 出列 3
• 第2轮：4,5,6 → 出列 6
• 第3轮：7,1,2 → 出列 2
• 第4轮：4,5,7 → 出列 7
• 第5轮：1,4,5 → 出列 5
• 第6轮：1,4,1 → 出列 1
• 最后剩下 4

出列顺序：3 → 6 → 2 → 7 → 5 → 1 → 4，选 A。

🎯 约瑟夫问题是循环链表的标志性考题，关键在于"出列后从下一个人重新开始报数"，用循环链表模拟最直观。数学公式法也可以求解（递推公式 f(n,m) = (f(n-1,m) + m) % n），但 GESP 五级阶段掌握链表模拟即可。

---

练习题 3（单选题）

题目： 关于链表和数组的比较，下列说法错误的是？（ ）

A. 数组支持随机访问，链表不支持
B. 在已知位置时，链表的插入删除比数组快
C. 链表的内存一定比数组占用少
D. 数组的内存是连续的，链表的内存是离散的

🔑 点击查看答案与解析

答案： C

解析：

• A 正确 ✅：数组可以通过下标直接访问（O(1)），链表必须从头遍历（O(n)）
• B 正确 ✅：链表插入删除只需要改指针（O(1)，已知位置），数组需要挪动元素（O(n)）
• C 错误 ❌：链表每个节点除了存数据还要存指针，反而可能占用更多内存
• D 正确 ✅：这是两者最根本的区别

🍎 生活比喻：数组像一排连在一起的储物柜，按编号直接找；链表像一串珍珠项链，要找某颗珍珠得顺着链子一颗一颗摸过去。

---

练习题 4（单选题）

题目： 在单链表中，删除指针 p 所指节点的后继节点，正确的操作顺序是？（ ）

A. p->next = p->next->next; delete p->next;
B. delete p->next; p->next = p->next->next;
C. ListNode* q = p->next; p->next = q->next; delete q;
D. ListNode* q = p->next; delete q; p->next = q->next;

🔑 点击查看答案与解析

答案： C

解析：

删除节点的正确步骤：

1. 先用临时指针 q 保存要删除的节点（防止丢失）
2. 把 p 的 next 指向 q 的下一个节点（跳过 q）
3. 释放 q 的内存

• A 错误：先改指针再 delete，这时候 p->next 已经变了，delete 的是新的后继节点
• B 错误：先 delete 再访问 p->next->next，此时 p->next 已经是野指针了
• C 正确 ✅：先暂存、再改指针、最后释放，三步完美
• D 错误：先 delete q，再访问 q->next，q 已经被释放了，是野指针

⚠️ 易错点：删除节点一定要先存后删！就像拆墙——先搭好脚手架（暂存），再拆旧墙（释放），不然会塌。

---

练习题 5（判断题）

题目： 单链表反转后，原来的尾节点变成了新的头节点。（ ）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 反转就是把所有指针方向反过来。原来头→...→尾，反转后变成尾→...→头，所以原来的尾节点成了新头，原来的头节点成了新尾（next 为 nullptr）。

💡 三指针反转法口诀：

• prev 追着 curr 跑，nextTemp 往前跳
• curr 回头指 prev，prev curr 各走一步

---

练习题 6（单选题）

题目： 在双链表中，在指针 p 所指节点后面插入新节点 s，正确的操作顺序是？（ ）

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

🔑 点击查看答案与解析

答案： B（同时 D 也能得到正确结果，本题原题存在两个正确答案）

解析：

双链表插入的关键：先连新节点的前后，再改前后节点的指针。

正确顺序（B选项）：

1. s->prev = p —— 新节点的前驱指向 p
2. s->next = p->next —— 新节点的后继指向 p 的后继
3. p->next->prev = s —— 后继节点的前驱指向 s
4. p->next = s —— p 的后继指向 s（这步放最后，因为改了 p->next 就找不到原来的后继了）

• A 错误：第 4 步先改了 p->next，再访问 p->next->prev 时，p->next 已经是 s 了，变成 s->prev = s，错！
• B 正确 ✅：先改后继节点的 prev，再改 p 的 next
• C 错误：第一步就改了 p->next，后面找不到原后继了
• D 也正确 ✅：四步执行后 p->next = s、s->prev = p、s->next = 原p->next、原p->next->prev = s，双向链接全部成立；只是它先改"旧后继的 prev"、再改"p 的 next"，顺序与 B 不同，但结果同样正确。因此本题 B 与 D 都是正确答案，原题不够严谨。

💡 记忆技巧：双链表插入 = 先给新节点找好前后邻居，再通知前后邻居换邻居。先通知后面的邻居（它的 prev 要改），最后通知前面的邻居（它的 next 要改）。

---

练习题 7（判断题）

题目： 循环单链表中，判断遍历结束的条件是 p->next == nullptr。（ ）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： 循环链表的尾节点 next 指向头节点，不是 nullptr。所以遍历循环链表的终止条件是 p == head 或 p->next == head（取决于从头开始还是从第二个开始）。

⚠️ 易错点：循环链表没有"尾"的概念，所有节点都连成一个环。遍历时要特别注意死循环——必须判断什么时候回到起点。

---

练习题 8（编程题）

题目： 请编写一个函数 int getLength(ListNode* head)，计算单链表的长度（节点个数）。

然后在主函数中：创建一个包含 5 个节点的链表（值为 1, 2, 3, 4, 5），调用函数输出长度。

提示：节点定义如下：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

🔑 点击查看答案与解析

参考答案：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int getLength(ListNode* head) {
    int len = 0;
    ListNode* p = head;
    while (p != nullptr) {
        len++;
        p = p->next;
    }
    return len;
}

int main() {
    // 创建链表 1->2->3->4->5
    ListNode* head = new ListNode(1);
    ListNode* tail = head;
    for (int i = 2; i <= 5; i++) {
        tail->next = new ListNode(i);
        tail = tail->next;
    }
    
    cout << "链表长度：" << getLength(head) << endl;
    return 0;
}

解析：

求长度是链表最基础的操作：

• 用一个指针 p 从头节点开始遍历
• 每经过一个节点，计数器 len 加 1
• p 走到 nullptr 时结束，返回 len

时间复杂度 O(n)，空间复杂度 O(1)。

💡 尾插法建表技巧：维护一个 tail 指针始终指向尾节点，每次新节点接到 tail 后面，然后 tail 后移。这样就不用每次都从头找尾了。

---

七、📊 考点总结表

考点	重要程度	出题形式	易错点
链表 vs 数组对比	⭐⭐⭐	选择/判断	各自优缺点记反
单链表节点定义	⭐⭐⭐	选择/代码填空	指针类型写错
单链表遍历	⭐⭐⭐⭐	程序阅读	终止条件 p!=nullptr
链表插入（头插/尾插/中间插）	⭐⭐⭐⭐	代码填空/编程题	指针修改顺序
链表删除	⭐⭐⭐⭐	选择/代码填空	先释放再改指针 → 野指针
链表反转（三指针法）	⭐⭐⭐⭐⭐	代码填空（高频）	三指针顺序搞混
双链表插入删除	⭐⭐⭐	选择/程序阅读	四个指针修改顺序
循环链表终止条件	⭐⭐⭐	判断/选择	和普通链表混淆
约瑟夫问题	⭐⭐⭐⭐	编程题/程序阅读	报数起始位置搞错
时间复杂度分析	⭐⭐⭐	选择	已知位置插入是O(1)，查找是O(n)

---

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│           链表 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. 数组：连续内存，随机访问O(1)，插入O(n)  │
│  2. 链表：离散内存，随机访问O(n)，插入O(1)  │
│  3. 链表节点 = 数据域 + 指针域              │
│  4. 单链表遍历：p从头走，p==nullptr就停     │
│  5. 头插法：新节点next=head; head=新节点    │
│  6. 删除节点：先暂存，再改指针，最后释放    │
│  7. 链表反转三指针：prev / curr / nextTemp  │
│  8. 反转核心：curr->next = prev             │
│  9. 反转后：原尾变新头，原头变新尾          │
│ 10. 双链表：每个节点有 prev 和 next 两个指针│
│ 11. 双链表插入：先连新节点，再改前后邻居    │
│ 12. 循环链表：尾节点next指向头节点          │
│ 13. 循环链表遍历：回到头节点就停止          │
│ 14. 约瑟夫问题：循环链表经典应用            │
│ 15. 链表操作最怕：野指针、内存泄漏          │
└─────────────────────────────────────────────┘

---