---
title: "链表"
description: "单链表、双链表与循环链表的实现，以及用数组模拟链表的写法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 链表

数组的优点是访问快，随便给个下标就能 $O(1)$ 拿到元素。它的缺点是插入和删除麻烦：往中间插一个元素，后面的都得往后挪。

链表换了个思路。它不要求元素连续存放，每个元素记住下一个元素在哪。这样插入和删除只需改几个「指针」，缺点是访问第 $k$ 个元素得从头一个个走过去。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

| 考试 | 大纲要求 | 本章位置 |
| --- | --- | --- |
| GESP C++ 五级 | 考点 3：链表的创建、插入、删除、遍历和反转，单链表、双链表、循环链表的区别 | 全章 |
| CSP-J/S 入门级 | 3.1 线性结构：单链表、双向链表、循环链表 | 全章 |

## 数组与链表的对比

| 对比项 | 数组 | 链表 |
| --- | --- | --- |
| 存储方式 | 连续内存 | 分散，靠指针连接 |
| 随机访问第 k 个 | $O(1)$ | $O(n)$ |
| 已知位置后插入或删除 | $O(n)$，要移动元素 | $O(1)$，只改指针 |
| 查找某个值 | $O(n)$ | $O(n)$ |
| 额外空间 | 无 | 每个节点多存一个指针 |

结论很简单：**经常随机访问就用数组，经常在中间插入删除就用链表**。竞赛里绝大多数情况数组更划算，链表更多出现在需要频繁增删的场景，以及初赛的阅读程序题里。

## 单链表

单链表的每个节点存两部分：数据，以及指向下一个节点的指针。

```cpp
struct Node {
    int data;    // 数据域
    Node *next;  // 指针域，指向下一个节点
};

一个链表用一个头指针标记起点。如果头指针是 `NULL`（或 `nullptr`），说明链表为空。

### 建立链表（头插法）

头插法每次把新节点放到最前面。读入 1 2 3，建出来的链表是 3 → 2 → 1。

```cpp
Node *head = NULL;
for (int i = 1; i <= n; i++) {
    Node *p = new Node;  // 申请一个新节点
    p->data = a[i];
    p->next = head;      // 新节点指向原来的头
    head = p;            // 头指针移到新节点
}

### 建立链表（尾插法）

尾插法保持读入顺序。读入 1 2 3，链表就是 1 → 2 → 3。

```cpp
Node *head = NULL, *tail = NULL;
for (int i = 1; i <= n; i++) {
    Node *p = new Node;
    p->data = a[i];
    p->next = NULL;
    if (head == NULL) {
        head = tail = p;  // 第一个节点
    } else {
        tail->next = p;   // 接到尾巴后面
        tail = p;         // 尾巴后移
    }
}

### 遍历

```cpp
for (Node *p = head; p != NULL; p = p->next) {
    cout << p->data << " ";
}

### 查找

```cpp
Node *find(Node *head, int x) {
    for (Node *p = head; p != NULL; p = p->next) {
        if (p->data == x) return p; // 找到就返回节点地址
    }
    return NULL; // 没找到
}

### 在节点 p 之后插入

```cpp
Node *q = new Node;
q->data = x;
q->next = p->next; // 先让新节点接上后面
p->next = q;       // 再让 p 指向新节点

这两行的顺序不能反。如果先写 `p->next = q`，原来 p 后面的那串节点就丢了。

### 删除节点 p 之后的节点

```cpp
Node *q = p->next;
p->next = q->next; // 跳过 q
delete q;          // 释放内存

### 删除头节点

头节点没有前驱，要单独处理。

```cpp
if (head != NULL) {
    Node *q = head;
    head = head->next;
    delete q;
}

这个「头节点要特殊处理」的麻烦，可以用一个不存数据的**虚拟头节点**（也叫哨兵）绕开，让所有节点的删除逻辑统一。

## 双向链表

双向链表的节点多存一个指向前驱的指针，可以往前也能往后走。

```cpp
struct DNode {
    int data;
    DNode *prev; // 指向前一个
    DNode *next; // 指向后一个
};

在节点 p 之后插入 q：

```cpp
q->next = p->next;
q->prev = p;
if (p->next != NULL) p->next->prev = q; // 后面还有节点才需要
p->next = q;

代价是每个节点多一个指针，插入删除要改更多地方，写错一处整条链就断了。

## 循环链表

循环链表把尾节点的 `next` 指回头节点，形成一个环。从任意一个节点出发，一直走都能回到自己。

循环链表没有天然的「末尾」，遍历时要记住起点，走到回到起点为止：

```cpp
Node *p = head;
do {
    cout << p->data << " ";
    p = p->next;
} while (p != head);

约瑟夫环问题用循环链表描述最自然。

## 反转单链表

经典题，也是初赛阅读程序的高频素材。

```cpp
Node *reverse(Node *head) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL) {
        Node *nxt = cur->next; // 先记住下一个
        cur->next = prev;      // 当前节点指向前一个
        prev = cur;            // prev 前进
        cur = nxt;             // cur 前进
    }
    return prev; // 新头指针
}

三根指针依次挪动，走完一遍就反转了，时间 $O(n)$，额外空间 $O(1)$。

## 用数组模拟链表

竞赛里 `new` 和 `delete` 很慢，而且容易忘记释放。常见做法是用两个数组模拟：一个存数据，一个存「下一个节点的下标」。

```cpp
const int N = 100005;
int val[N], nxt[N];
int head = -1, cnt = 0; // head = -1 表示空链表

void insert_head(int x) {  // 头插
    val[cnt] = x;
    nxt[cnt] = head;
    head = cnt++;
}

void insert_after(int p, int x) { // 在 p 之后插入
    val[cnt] = x;
    nxt[cnt] = nxt[p];
    nxt[p] = cnt++;
}

void erase_after(int p) { // 删除 p 之后的节点
    nxt[p] = nxt[nxt[p]];
}

用 `-1` 表示「没有下一个」，遍历时判断 `p != -1` 即可。这种写法在初赛阅读程序里很常见，看到两个数组加一个 `nxt`，基本就是链表。

## 复杂度

| 操作 | 单链表 | 双向链表 |
| --- | --- | --- |
| 访问第 k 个 | $O(n)$ | $O(n)$ |
| 已知位置插入/删除 | $O(1)$ | $O(1)$ |
| 在头部插入/删除 | $O(1)$ | $O(1)$ |
| 遍历整个链表 | $O(n)$ | $O(n)$ |

## 常见易错点

- 插入时先接后面再接前面，顺序反了会丢链。
- 删除后要 `delete`，或者改用数组模拟。
- 头节点、尾节点要单独处理，忘了就崩。
- 遍历循环链表不能用 `p != NULL`，永远为真，要用起点判断。
- `->` 和 `.` 别混：指针访问成员用 `->`，对象访问成员用 `.`。
- 链表不支持下标访问，`l[i]` 这种写法只属于数组和 `vector`。
- **反转链表时先改指针、后存后继**。顺序反了就直接丢链，后面的节点全找不回来。
- **数组模拟链表用 `0` 表示空**。`0` 是合法下标，必须用 `-1` 表示「没有下一个」。
- **约瑟夫环走了 $m$ 步而不是 $m-1$ 步**。当前节点自己已经报了 1。
- **循环链表删除后忘记维护前驱**。单向链表没法回头，`prev` 要在移动时顺手记下来。

## 练习

### 练习 1：反转单链表

#### 题目描述

给定 $n$ 个整数，用链表存储，把它们**反转**后输出。

#### 输入格式

第一行一个整数 $n$；第二行 $n$ 个整数。

#### 输出格式

输出一行 $n$ 个整数，为反转后的序列。

#### 输入输出样例

输入

```
5
1 2 3 4 5

输出

```
5 4 3 2 1

#### 数据范围

- $1 \le n \le 10^5$，元素在 `int` 范围内。

#### 题目分析

反转链表是链表操作里**最经典、也最能考出「你有没有真的理解指针」** 的一道题。核心是**三指针法**：

- `prev`：已经反转好的部分的头（初始为「空」）；
- `cur`：当前要处理的节点；
- `nxt`：暂存 `cur` 的下一个节点（**必须先存下来**，因为 `cur->next` 马上就要被改掉）。

每一步做三件事：

1. 先把 `cur` 的下一个节点存进 `nxt`（不然改完就找不到了）；
2. 把 `cur` 的 `next` 指向 `prev`（完成这一步的反转）；
3. `prev` 和 `cur` 各往前走一格。

走完一遍，`prev` 就是新链表的头。

**为什么第 1 步不能省？** 这是链表题最典型的坑：一旦写下 `cur->next = prev`，原来的后继就永久丢失了，后面的节点全部「断链」找不回来。

**用数组模拟的写法**（竞赛里更常用，避免 `new` 的开销）只需要把「指针」换成「下标」：

```cpp
int prev = -1, cur = head;
while (cur != -1) {
    int nx = nxt[cur];   // 1. 存后继
    nxt[cur] = prev;     // 2. 反转指向
    prev = cur;          // 3. 前进
    cur = nx;
}
head = prev;             // 新的头

**注意用 `-1` 表示空**（而不是 `0`），因为 `0` 是合法的数组下标。这个约定和正文一致。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/linked-list/index.md

### 练习 2：约瑟夫环（循环链表）

在线评测练习：[P1423 报数出圈](https://dailyup.run/tasks/507)

#### 题目描述

$n$ 个小朋友围成一圈，编号从 $1$ 到 $n$。从 $1$ 号开始顺时针报数，报到 $m$ 的人出圈，他旁边的人从 $1$ 重新开始报数。按顺序输出所有出圈的小朋友的编号。

#### 输入格式

输入一行，包含两个正整数 $n$ 和 $m$，中间用一个空格隔开。

#### 输出格式

输出一行，包含 $n$ 个整数，依次为出圈的小朋友的编号，相邻两个整数之间用一个空格隔开。

#### 输入输出样例

输入

```
5 3

输出

```
3 1 5 2 4

输入

```
1 1

输出

```
1

#### 数据范围

- $1 \le n \le 1000$，$1 \le m \le 1000$。

#### 题目分析

**这是「循环链表」最标准的应用场景**：一圈人天然对应一个首尾相连的链表，出圈就是「删除一个节点」，然后从下一个节点接着数。

用数组模拟循环链表，写法比真指针干净得多：

1. **建表**：`nxt[i] = i + 1`，最后 `nxt[n] = 1`（首尾相连）；
2. **循环 $n$ 次**，每次：
   - 走 $m - 1$ 步（因为**当前这个人自己就报了 1**，所以只需再走 $m-1$ 步）；
   - 输出当前节点，然后**把它从链表里删掉**：`nxt[prev] = nxt[cur]`；
   - `cur` 移到下一个节点，继续。
3. 因为**只有一个人时** `nxt[cur] = cur`（自己指向自己），删除后仍然指向自己，所以循环能自然终止。

**最容易错的两个地方：**

1. **走 $m-1$ 步而不是 $m$ 步**。想一想：`cur` 指向的人现在报的是 1，报 2 要走到下一个，……，报到 $m$ 一共走了 $m-1$ 步。
2. **删除时要维护 `prev`**。数组模拟的单向循环链表没法回头，所以循环里要始终记住「当前节点的前一个」：

```cpp
for (int step = 1; step < m; step++) {
    prev = cur;        // 记住前驱
    cur = nxt[cur];    // 前进
}
nxt[prev] = nxt[cur];  // 删除 cur
cur = nxt[cur];        // 从下一个继续

**为什么不用双向链表或直接 `vector` 删除？** `vector` 删除中间元素是 $O(n)$，总复杂度 $O(n^2)$ 到 $O(n^3)$；链表删除是 $O(1)$。本题 $n \le 1000$ 用 `vector` 也能过，但**链表才是这个问题的「正确」数据结构**——这也是本章为什么把约瑟夫环放在链表这一节。

> 想进一步优化到 $O(n)$，需要用「递推公式」$f(n) = (f(n-1) + m) \bmod n$（只能求最后剩下的那个人，不能输出全部出圈顺序）。见《找规律与打表》那一章的示例。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/linked-list/index.md

## 小结

- 链表用指针把分散的节点串起来，插入删除 $O(1)$，但随机访问要 $O(n)$。
- 单链表只能往后走，双向链表能双向走，循环链表首尾相连。
- 头插法会反转顺序，尾插法保持顺序。
- 竞赛里常用两个数组模拟链表，避免 `new` / `delete` 的开销。
- 反转链表用三指针法，**必须先把后继存下来**再改指针，否则会断链。
- 约瑟夫环用循环链表：`nxt[n] = 1` 首尾相连，出圈就是删除节点，注意「走 $m-1$ 步」和维护前驱。
- 用数组模拟时用 `-1` 表示「空」，不要用 `0`（`0` 是合法下标）。

Source: https://cppguide.xyz/ds/linked-list/index.mdx
