链表
知识总结
链表的定义
链表是一种线性数据结构，由一系列节点组成。每个节点包含：
- 数据域：存储数据
- 指针域：指向下一个节点的地址
链表 vs 数组
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存 | 连续 | 不连续 |
| 访问第i个元素 | O(1) | O(n) |
| 插入/删除 | O(n) | O(1)（已知位置时） |
| 空间 | 固定大小 | 动态分配 |
链表类型
- 单链表：每个节点只有一个next指针
- 双链表：每个节点有prev和next两个指针
- 循环链表：尾节点的next指向头节点
链表基本操作
1struct Node {
2 int data;
3 Node* next;
4};
5
6// 头插法
7void insertHead(Node*& head, int val) {
8 Node* newNode = new Node{val, head};
9 head = newNode;
10}
11
12// 删除节点
13void deleteNode(Node*& head, int val) {
14 if (!head) return;
15 if (head->data == val) {
16 Node* temp = head;
17 head = head->next;
18 delete temp;
19 return;
20 }
21 Node* cur = head;
22 while (cur->next && cur->next->data != val)
23 cur = cur->next;
24 if (cur->next) {
25 Node* temp = cur->next;
26 cur->next = temp->next;
27 delete temp;
28 }
29}初赛常考题型
- 链表的插入/删除后指针的变化
- 给定操作序列，求链表最终状态
- 单链表反转的步骤分析