链表

1. 链表是什么？

1.1 数组的局限性

在探讨链表之前，我们首先需要理解其“对手”——数组（Array）的特性及其固有的局限性。数组在内存中是一段连续的空间，这为它带来了极高的随机访问效率。给定一个索引 $i$，我们可以在 $O(1)$ 时间内直接计算出地址并访问元素 a[i]。

然而，也正是“连续存储”这一特性，给数组带来了两个主要问题：

1. 大小固定：数组在创建时通常需要指定一个固定的大小。如果初始分配过小，当数据量超出预期时，就需要重新分配一个更大的数组，并将所有旧数据复制过去，这个过程的开销是昂贵的。如果分配过大，则会浪费大量内存空间。
2. 插入与删除低效：假设我们要在数组的第 $k$ 个位置插入一个新元素。为了保持数组的连续性，我们需要将从第 $k$ 个位置开始的所有元素都向后移动一位。这个操作的时间复杂度是 $O(N)$，其中 $N$ 是数组的长度。删除元素也面临同样的问题，需要移动后续元素来填补空缺，时间复杂度同样是 $O(N)$。

当我们需要频繁地进行插入和删除操作时，数组的性能瓶颈就暴露无遗。为了解决这个问题，链表应运而生。

1.2 链表的“指针”思想

链表的核心思想是放弃对连续内存的苛求。它的元素（我们称之为“节点”）可以散布在内存的任何位置。那么，如何将这些零散的节点组织成一个有序的序列呢？

答案是“指针”或“引用”。

想象一个寻宝游戏：你手上有第一张藏宝图（第一个节点），它告诉你宝藏（数据）的位置，并且在图的背面写着下一张藏宝图的隐藏地点（指向下一个节点的指针）。你根据指引找到第二张藏宝图，它同样包含着宝藏和指向下一张图的线索。如此往复，直到你找到一张背面写着“游戏结束”（空指针）的图，整个寻宝过程就结束了。

在这个比喻中：

• 每一张藏宝图 就是一个 节点 (Node)。
• 宝藏 就是节点中存储的 数据 (Data)。
• 下一张图的隐藏地点 就是指向下一个节点的 指针 (Pointer)。

通过这种方式，即使节点在内存中是离散存储的，我们也能通过指针将它们串联成一个逻辑上的线性序列。

1.3 节点：链表的基本单位

一个最简单的链表节点（Singly Linked List Node）由两部分构成：

1. 数据域 (Data Field)：用于存储元素的值。它可以是整数、字符、或者更复杂的结构体。
2. 指针域 (Pointer Field)：用于存储下一个节点的内存地址。我们通常称之为 next 指针。

整个链表由一个指向第一个节点的“头指针”（head）来标识。链表的末尾节点的 next 指针通常指向一个特殊的值，如 NULL（在动态链表中）或一个特殊标记（如 -1 或 0，在静态链表中），表示链表的结束。

1.4 静态链表 vs. 动态链表

实现链表主要有两种方式：

1. 动态链表 (Dynamic Linked List)：这是教科书中最标准的实现方式。使用 new (C++) 或 malloc (C) 在程序运行时动态地申请内存来创建每一个节点。这种方式灵活，可以根据需要创建任意数量的节点，直到内存耗尽。其缺点是频繁的内存申请和释放会带来一些性能开销，且涉及到底层内存管理，容易出错（如内存泄漏）。

2. 静态链表 (Static Linked List)：在算法竞赛中，为了追求极致的效率和编码的简洁性，选手们常常使用数组来模拟链表，这被称为“静态链表”。我们预先开辟一个足够大的数组（例如，大小为 $10^5+10$），数组的每个元素模拟一个节点。指针域不再存储内存地址，而是存储下一个节点在数组中的索引 (index)。这种方式避免了动态内存分配的开销，运行速度更快，代码也更简短。其缺点是链表的总容量受限于预先开辟的数组大小。

对于初学者和竞赛选手而言，掌握静态链表的实现至关重要。

2. 静态链表的实现

我们将使用两个数组 val[] 和 nxt[] 来模拟链表。

• val[i]：存储索引为 $i$ 的节点的数据值。
• nxt[i]：存储索引为 $i$ 的节点的下一个节点在数组中的索引。
• head：一个整型变量，存储头节点的索引。
• idx：一个整型变量，表示下一个可用的（尚未被分配的）节点的索引。

2.1 核心操作

我们定义几个核心操作，并用代码实现它们。

初始化

开始时，链表为空。我们将 head 初始化为一个特殊值（如 -1）表示空链表。idx 从一个确定的值（如 0 或 1）开始，用于分配新节点。

int head, val[N], nxt[N], idx;

void init() {
    head = -1; // 头指针指向-1，表示空
    idx = 0;   // 0号索引是第一个可用的位置
}

在表头插入

要在链表头部插入一个值为 x 的新节点：

1. 从备用空间中取出一个新节点，其索引为 idx。
2. 将新节点的值设为 x，即 val[idx] = x。
3. 将新节点的 next 指针指向原来的头节点，即 nxt[idx] = head。
4. 更新头指针，使其指向这个新节点，即 head = idx。
5. 将 idx 自增，为下一次分配做准备。

// 在表头插入一个数x
void add_head(int x) {
    val[idx] = x;     // 新节点存值
    nxt[idx] = head;  // 新节点的next指向旧的头
    head = idx;       // head更新为新节点
    idx++;            // 可用节点索引后移
}

这个过程的时间复杂度是 $O(1)$。

在任意位置后插入

要在索引为 $k$ 的节点后面插入一个值为 $x$ 的新节点：

1. 分配一个新节点 idx，并赋值 val[idx] = x。
2. 将新节点的 next 指针指向 $k$ 节点的下一个节点，即 nxt[idx] = nxt[k]。
3. 将 $k$ 节点的 next 指针指向新节点，即 nxt[k] = idx。
4. idx 自增。

// 在索引为k的节点后插入一个数x
void add(int k, int x) {
    val[idx] = x;      // 赋值
    nxt[idx] = nxt[k]; // 新节点的next指向k的next
    nxt[k] = idx;      // k的next指向新节点
    idx++;
}

这个过程的时间复杂度也是 $O(1)$。注意，这里的前提是已经知道了 $k$ 的索引。如果只知道是第几个节点，则需要先遍历找到它。

删除任意位置后的节点

要删除索引为 $k$ 的节点后面的那个节点：

1. 将被删除节点的索引是 nxt[k]。
2. 我们只需要绕过这个节点即可：将 $k$ 节点的 next 指针，直接指向被删除节点的下一个节点。
3. 即 nxt[k] = nxt[nxt[k]]。

// 删除索引为k的节点后面的节点
void del(int k) {
    nxt[k] = nxt[nxt[k]]; // k的next指向下下个节点
}

这个过程的时间复杂度同样是 $O(1)$。被“删除”的节点并未从数组中移除，它只是从链中断开，成为了“孤儿”节点。在静态链表中，我们通常不重用这些节点，因为管理一个可重用节点池（“空闲链表”）会增加代码的复杂性。

遍历链表

从头指针 head 开始，沿着 nxt 数组不断移动，直到遇到结束标记 -1。

void traverse() {
    for (int i = head; i != -1; i = nxt[i]) {
        cout << val[i] << " ";
    }
    cout << endl;
}

2.2 静态链表完整代码示例

题意概括：实现一个单链表，支持在表头插入、删除第 $k$ 个插入的数后面的数、在第 $k$ 个插入的数后插入一个数。共 $M$ 次操作。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100010; // 数组大小，通常比题目数据范围大一些
int head, val[N], nxt[N], idx;
int k, x; // 操作需要的变量

// 初始化
void init() {
    head = -1;
    idx = 0;
}

// 头插法
void add_h(int v) {
    val[idx] = v;
    nxt[idx] = head;
    head = idx++;
}

// 在第p个插入的数(索引p-1)后插入一个数
void add_k(int p, int v) {
    val[idx] = v;
    nxt[idx] = nxt[p];
    nxt[p] = idx++;
}

// 删除第p个插入的数(索引p-1)后的数
void del_k(int p) {
    nxt[p] = nxt[nxt[p]];
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    init();
    int m;
    cin >> m;
    while (m--) {
        char op;
        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_h(x);
        } else if (op == 'D') {
            cin >> k;
            if (k == 0) head = nxt[head]; // k=0表示删除头节点
            else del_k(k - 1); // 题目k是第k个插入的数，索引是k-1
        } else { // op == 'I'
            cin >> k >> x;
            add_k(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = nxt[i]) {
        cout << val[i] << " ";
    }
    cout << endl;

    return 0;
}

• 复杂度分析：
  • 时间复杂度：每次操作（插入、删除）都是 $O(1)$。总共 $M$ 次操作，总时间复杂度为 $O(M)$。遍历输出为 $O(N)$，其中 $N$ 是链表最终的节点数。
  • 空间复杂度：$O(N)$，用于存储链表节点的数组。

3. 动态链表的实现

动态链表是使用指针和 struct 实现的，是C++/C语言中链表的标准形态。

3.1 struct 与指针

我们首先定义一个节点结构体 Node。

struct Node {
    int val;    // 数据域
    Node* nxt;  // 指针域，指向下一个Node类型的对象

    // 构造函数，方便创建新节点
    Node(int v) : val(v), nxt(nullptr) {} 
};

• Node* 是一种类型，表示“指向 Node 对象的指针”。
• nullptr 是C++11引入的空指针常量，功能上等价于 NULL。

3.2 动态内存分配 (new)

使用 new 关键字可以在程序的“堆”内存中申请一块空间来创建一个 Node 对象，并返回指向该对象的指针。

Node* p = new Node(10); // 创建一个新节点，值为10，p指向它

使用完毕后，需要用 delete p; 来释放这块内存，防止内存泄漏。但在算法竞赛中，通常程序运行时间很短，结束时操作系统会自动回收所有内存，所以有时会省略 delete。

3.3 核心操作（动态版）

与静态链表逻辑一致，只是语法不同。

• 头指针：Node* head = nullptr;
• 头插：

  Node* newNode = new Node(x);
  newNode->nxt = head;
  head = newNode;
  

• 在节点p后插入：

  Node* newNode = new Node(x);
  newNode->nxt = p->nxt;
  p->nxt = newNode;
  

• 删除节点p后的节点：

  Node* tmp = p->nxt; // 要删除的节点
  if (tmp != nullptr) {
      p->nxt = tmp->nxt;
      delete tmp; // 释放内存
  }
  

3.4 动态链表代码示例

用动态链表重写上面的题目。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 节点定义
struct Node {
    int val;
    Node* nxt;
    Node(int v) : val(v), nxt(nullptr) {}
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    Node* head = nullptr; // 头指针
    map<int, Node*> mp;   // 模拟静态链表的索引查找，k -> Node*
    int cnt = 0;          // 记录插入了多少个数，用于映射k

    int m;
    cin >> m;
    while (m--) {
        char op;
        cin >> op;
        if (op == 'H') {
            int x;
            cin >> x;
            Node* cur = new Node(x);
            cur->nxt = head;
            head = cur;
            cnt++;
            mp[cnt] = cur;
        } else if (op == 'D') {
            int k;
            cin >> k;
            if (k == 0) {
                if (head) {
                    Node* tmp = head;
                    head = head->nxt;
                    // delete tmp; // 竞赛中可省略
                }
            } else {
                Node* p = mp[k];
                if (p && p->nxt) {
                    Node* tmp = p->nxt;
                    p->nxt = tmp->nxt;
                    // delete tmp;
                }
            }
        } else { // op == 'I'
            int k, x;
            cin >> k >> x;
            Node* p = mp[k];
            if (p) {
                Node* cur = new Node(x);
                cur->nxt = p->nxt;
                p->nxt = cur;
                cnt++;
                mp[cnt] = cur;
            }
        }
    }
    
    Node* cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->nxt;
    }
    cout << endl;
    
    // 清理内存（在实际工程中是必要的）
    // while(head) {
    //     Node* tmp = head;
    //     head = head->nxt;
    //     delete tmp;
    // }

    return 0;
}

• 复杂度分析：
  • 时间复杂度：由于需要通过 map 来查找第 $k$ 个插入的节点，map 的操作是 $O(\log k)$。所以 $M$ 次操作的总时间复杂度是 $O(M \log N)$。如果不使用 map 而使用数组，可以做到 $O(M)$。
  • 空间复杂度：$O(N)$，用于存储节点和 map。

4. 常见链表变体

4.1 双向链表 (Doubly Linked List)

单向链表的一个缺点是只能单向移动。如果要删除某个节点，或者访问它的前一个节点，必须从头开始遍历，很不方便。双向链表解决了这个问题。

双向链表的节点在单向链表的基础上，增加了一个指向前一个节点的指针，通常称为 prev。

• 节点结构：Data, next, prev。
• 优点：
  • 可以双向遍历。
  • 删除一个已知指针的节点 p 是 $O(1)$ 操作，不再需要知道其前驱。操作为：p->prev->next = p->next; p->next->prev = p->prev;

4.1.1 静态实现

需要额外一个 prv[] 数组。

// val[], nxt[], prv[]
// 在索引p后插入新节点idx
void add(int p, int v) {
    val[idx] = v;
    // 连接新节点与后继
    nxt[idx] = nxt[p];
    prv[nxt[p]] = idx;
    // 连接新节点与前驱
    nxt[p] = idx;
    prv[idx] = p;
    idx++;
}

// 删除索引p的节点
void del(int p) {
    nxt[prv[p]] = nxt[p];
    prv[nxt[p]] = prv[p];
}

删除操作变得非常对称和优雅。

4.1.2 动态实现

struct 中增加一个 Node* prv; 成员。

struct Node {
    int val;
    Node *nxt, *prv;
    Node(int v) : val(v), nxt(nullptr), prv(nullptr) {}
};

// 删除节点p
void del(Node* p) {
    if (p->prv) p->prv->nxt = p->nxt;
    if (p->nxt) p->nxt->prv = p->prv;
    // delete p;
}

4.2 循环链表 (Circular Linked List)

循环链表的特点是，最后一个节点的 next 指针不再是 NULL 或 -1，而是指向头节点。这样，整个链表形成一个环。

• 优点：从任意一个节点出发，都可以遍历整个链表。
• 注意：遍历时要小心，终止条件不再是 p == nullptr，而是 p->nxt == head（遍历一圈后回到起点）。

4.3 应用场景：约瑟夫问题

题意概括：$N$ 个人围成一圈，从第 1 个人开始报数，报到 $M$ 的人出局，他下一个人再从 1 开始报数，如此反复，直到所有人出局。求出局序列。

这个问题是循环链表的经典应用。用循环链表模拟这个过程非常直观。

C++ 代码示例（静态循环链表）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;

    // 静态数组模拟循环链表
    vector<int> nxt(n + 1);
    for (int i = 1; i <= n; ++i) {
        nxt[i] = (i % n) + 1; // i的下一个是i+1, n的下一个是1
    }

    int cur = n; // cur指向当前报数人的前一个。开始时1号报数，cur指向n。
    cout << "出局顺序: ";
    for (int i = 0; i < n; ++i) {
        // 走 m-1 步找到要出局的人的前一个
        for (int j = 0; j < m - 1; ++j) {
            cur = nxt[cur];
        }
        
        // cur 的下一个节点 p 就是要出局的人
        int p = nxt[cur];
        cout << p << " ";
        
        // 删除 p
        nxt[cur] = nxt[p];
    }
    cout << endl;

    return 0;
}

• 复杂度分析：
  • 时间复杂度：总共有 $N$ 个人出局。每找一个人，需要报数 $M$ 次，即在链表上走 $M-1$ 步。所以总时间复杂度是 $O(N \times M)$。
  • 空间复杂度：$O(N)$，用于存储链表。

5. 例题

5.1 选择题与判断题

例1：(判断题) 在一个长度为 $N$ 的单链表中，访问第 $k$ 个元素的时间复杂度是 $O(1)$。

• 答案：错误。
• 解析：链表的内存不连续，无法通过地址计算直接访问。要访问第 $k$ 个元素，必须从头节点 head 开始，沿着 next 指针移动 $k-1$ 次。因此，时间复杂度是 $O(k)$，最坏情况下是 $O(N)$。

例2：(选择题) 对于一个不带头结点的单链表，在指针 p 所指向的节点之后插入一个新节点 s，正确的操作序列是？ A. p->next = s; s->next = p->next; B. s->next = p->next; p->next = s; C. p->next = s->next; s->next = p; D. s->next = p; p->next = s;

• 答案：B。
• 解析：必须先将新节点 s 的 next 指向 p 原来的后继 p->next，以防止链表“断裂”。然后再将 p 的 next 指向 s。如果先执行 p->next = s;，那么 p 原来的后继节点的地址就会丢失。

5.2 程序阅读题

题意概括：阅读下列反转单链表的函数，并说明其功能。假设链表头指针为 head。

Node* rev(Node* hed) {
    Node *pre = nullptr;
    Node *cur = hed;
    while (cur != nullptr) {
        Node* nxt = cur->nxt; // 备份下一个节点
        cur->nxt = pre;       // 当前节点指向前一个
        pre = cur;            // pre后移
        cur = nxt;            // cur后移
    }
    return pre; // 返回新的头节点
}

• 答案：该函数的功能是反转一个单链表，并返回反转后新链表的头节点。
• 解析：
  1. pre 指针用于保存当前节点 cur 的前驱节点，初始为 nullptr。
  2. cur 指针是工作指针，从头节点开始遍历。
  3. 循环内部：
     • Node* nxt = cur->nxt;：至关重要的一步。因为下一步 cur->nxt 将被修改，所以必须先用 nxt 临时保存 cur 的原始后继节点，以防链表丢失。
     • cur->nxt = pre;：反转操作的核心，将当前节点的 next 指针指向它的前驱。
     • pre = cur; 和 cur = nxt;：将 pre 和 cur 指针都向后移动一步，为处理下一个节点做准备。
  4. 循环结束后，cur 变为 nullptr，而 pre 正好指向原始链表的最后一个节点，也就是新链表的头节点。

5.3 程序补全题

题意概括：补全以下合并两个有序单链表 l1 和 l2 的函数代码。函数应返回合并后新链表的头节点。

#include<bits/stdc++.h>
using namespace std;

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

Node* merge(Node* l1, Node* l2) {
    Node* dum = new Node(0); // 创建一个哨兵节点(dummy node)
    Node* cur = dum;
    
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val < l2->val) {
            cur->nxt = l1;
            l1 = l1->nxt;
        } else {
            cur->nxt = l2;
            l2 = l2->nxt;
        }
        cur = cur->nxt;
    }
    
    // ___________________  // 在此处补全代码

    return dum->nxt;
}

• 答案：cur->nxt = (l1 != nullptr) ? l1 : l2;
• 解析：
  1. 当 while 循环结束时，意味着 l1 和 l2 中至少有一个已经遍历到了末尾 (nullptr)。
  2. 此时，另一个链表可能还有剩余的节点。因为两个链表本身都是有序的，所以这个剩余的部分也必然是有序的，并且其所有元素都大于或等于已合并部分的最后一个元素。
  3. 因此，我们不需要再逐个比较。只需要将 cur (合并后链表的尾节点) 的 next 指针，直接指向那个非空的链表头即可。
  4. l1 != nullptr ? l1 : l2 是一个三元运算符，优雅地实现了这个逻辑：如果 l1 不是空，就接上 l1；否则就接上 l2。也可以写成 if (l1) cur->nxt = l1; else cur->nxt = l2;。

6. 总结与复杂度分析

6.1 链表 vs. 数组

特性	数组 (Array)	链表 (Linked List)
内存布局	连续	离散
大小	固定	动态
随机访问 (访问第 $k$ 个)	$O(1)$	$O(N)$
查找元素 (给定值)	$O(N)$
插入/删除 (在头部)		$O(1)$
插入/删除 (在尾部)	$O(1)$ (若有尾指针)	$O(N)$ (单链表), $O(1)$ (有尾指针)
插入/删除 (在中间，已知位置)	$O(N)$	$O(1)$ (双向链表), $O(1)$ (单链表已知前驱)

6.2 学习建议

链表的核心在于对“指针”（或索引）的理解和操作。它的逻辑性远强于其代码的复杂度。

1. 画图：在处理任何链表问题时，务必在纸上画出节点和指针。用箭头清晰地表示 next 和 prev 的指向。模拟每一步操作（如插入、删除、反转），观察箭头的变化。这是理解链表最有效的方法。
2. 熟练实现：反复练习静态链表、动态链表、双向链表、循环链表的基本操作，直到能够不假思索地写出代码。
3. 掌握经典问题：链表反转、合并有序链表、判断链表是否有环、寻找环的入口、删除倒数第 $k$ 个节点等，都是必须掌握的经典模型。它们是更复杂问题的基础。
4. 注意边界：链表问题常常在边界条件下出错。要特别注意：
   • 链表为空 (head == nullptr)
   • 链表只有一个节点
   • 操作发生在头节点
   • 操作发生在尾节点