讲解

创建链表的方式

面试题会用到的，但是笔试题不会用的：

// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

但是这种动态的方式会很麻烦，而且大多数情况下会超时。数组模拟一切，可以改进一下，用数组来模拟链表：

用数组模拟单链表

单链表最主要的方式是邻接表，邻接表最主要的功能是存储图和树。

单链表的结构图示如下：

头节点一开始指向一个空节点，每次都会往里新插入一个元素。每个点里面都会有两个值（val与next指针）。

接下来我们用e[N]表示某个点的值是多少，用ne[N]表示某个点的next指针指向的值是多少。这两者之间是用下标关联起来的。空节点的下标使用-1来表示。例子如下：

由此就提取出了链表在数组中的表达式。

初始化链表的写法：

// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针指向的节点的下标值是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化链表
void init() {
    // 头节点一开始指向空集
    head = -1;
    // 从0号点开始分配
    idx = 0;
}

将元素插到头节点后的写法

// 将x插到头节点
void add_to_head(int x) {
    e[idx] = x; // 将要插入的节点x存下来
    ne[idx] =  head; // 将插入节点的指针指向head指向的值
    head = idx; // 让head指针指向插入元素
    idx++; // idx位置已用过，就移到下一个位置
}

将元素插入到任意节点后的方法

// 将x插到下标为k的节点的后面
void add(int k, int x) {
    e[idx] = x; // 将要插入的节点x存下来
    ne[idx] =  ne[k]; // 将插入节点的指针指向k指向的值
    ne[k] = idx; // 让k指针指向插入元素
    idx++; // idx位置已用过，就移到下一个位置
}

将下标是k的点后面的点删掉的方法

// 将下标是k的点后面的点删掉
void remove(int k) {
    ne[k] = ne[ne[k]]; // 跳过两个指针就可以实现删除
}

用数组模拟双链表

双链表的作用是优化问题。双链表就是一个节点有两个指针，一个指向前，另一个指向后。

// 初始化
void init() {
	// 0表示左端点，1表示右端点
	r[0] = 1; l[1] = 0;
	idx = 2;
}

// 在下标是k的点右边插入x
void add(int k, int x) {
	e[idx] = x;
	r[idx] = r[x];
	l[idx] = k;
	l[r[k]] = idx;
	r[k] = idx;
}

// 删除第k个点
void remove(int k) {
	r[l[k]] = r[k];
	l[r[k]] = l[k];
}

模板题

826. 单链表 - AcWing题库

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

const int N = 100010;

// head 表示头节点下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针指向的节点的下标值是多少
// idx 存储当前已经用到了哪个点
int head, idx, e[N], ne[N];

// 初始化链表
void init() {
	// 头节点一开始指向空集
	head = -1;
	// 从0号节点开始分配
	idx = 0;
}

// 将x插到头节点
void add_to_head(int x) {
	e[idx] = x; // 将要插入的节点x存下来
	ne[idx] = head; // 将插入节点的指针指向head指向的值
	head = idx; // 让head指针指向插入元素
	idx++; // idx位置已用过，就移到下一个位置
}

// 将元素插入到任意节点后的方法
void add(int k, int x) {
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx++;
}

// 将下标是k的点后面的点删掉的方法
void remove(int k) {
	ne[k] = ne[ne[k]]; // 跳过两个指针就可以实现删除
}

int main() {
	int m;
	cin >> m;
	init();
	while(m--){
		int k, x;
		char op;
		cin >> op;
		if (op == 'H') {
			cin >> x;
			add_to_head(x);
		} else if (op == 'D'){
			cin >> k;
			// 注意：下标是从0开始
			if (!k)  head = ne[head];
			remove(k - 1);
		} else {
			cin >> k >> x;
			add(k - 1, x);
		}
	}
	for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
	cout << endl;
	return 0;
}

解释一下一个关键的地方：

if (!k) head = ne[head];   // 如果 k 是 0，就删除头节点
remove(k - 1);             // 否则删除第 k 个插入的数后面的节点

情况1：k == 0

if (!k) head = ne[head];

• !k 就是 k == 0
• head = ne[head]：把头指针指向原来的头的下一个
• 相当于：跳过头节点，实现“删除头节点”

举例： 链表：6 → 5 → 4 → NULL，head = 2（假设6在2号盒子） 执行 D 0：

• head = ne[head] = ne[2] = 1（假设5在1号盒子）
• 现在头变成1号盒子（5），6被删了

情况2：k > 0

remove(k - 1);

• k-1 是“第k个插入的数”对应的下标
• remove(k-1)：删掉这个节点后面的节点

举例： D 2：删除第2个插入的数后面的数

• 第2个插入的数 → 下标是 1
• 调用 remove(1) → 把下标1的节点的下一个删掉

为什么不能统一用 remove(k-1) 处理 k=0？

• k=0 时，k-1 = -1
• remove(-1) 会访问 ne[-1] → 越界！

所以必须单独处理 k=0 的情况。这里如果看不懂多看就行了。

827. 双链表 - AcWing题库

// 删除链表节点的逻辑实现
void remove(int k) {
    // 左边的右边直接等于右边
    r[l[k]] = r[k];
    // 右边的左边直接为左边
    l[r[k]] = l[k];
}

// 插入
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[idx]] = idx;
    r[k] = idx;
    idx++;
}

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

const int N = 100010;

// 点存的值，左右指针，当前用到的下标
int e[N], l[N], r[N], idx;

// 初始化
void init() {
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 插入
void add(int k, int x) {
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

// 删除链表节点的逻辑实现
void remove(int k) {
    // 左边的右边直接等于右边
    r[l[k]] = r[k];
    // 右边的左边直接为左边
    l[r[k]] = l[k];
}

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        string op;
        int k, x;
        cin >> op;
        if (op == "L") {
            cin >> x;
            add(0, x);
        } else if (op == "R") {
            cin >> x;
            add(l[1], x);
        } else if (op == "D") {
            cin >> k;
            remove(k + 1);
        } else if (op == "IL") {
            add(l[k + 1], x);
        } else {
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for (int i = r[0]; i != 1; i = r[i]) {
        cout << e[i] << ' ';
    }
    cout << endl;
    return 0;
}