链表
链表的基础知识
- 链表节点需存储值和一个next指针，所以在相同数据量下，链表比数组占用更多空间；
- 在链表中插入/删除元素的时间复杂度为；
- 在链表中访问/查找元素的时间复杂度为；
链表与数组
| 对比项 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续的内存空间 | 非连续的内存空间，通过节点的指针连接 |
| 随机访问 | 支持随机访问，可以通过下标在 时间内访问任意元素 | 不支持随机访问，访问特定元素需要从链表头开始遍历，时间复杂度为 |
| 插入/删除操作 | 在中间位置插入或删除元素时，需要移动大量元素，时间复杂度为 | 只需要修改指针，时间复杂度为 （在已知节点位置的情况下） |
| 内存分配 | 分配连续的大块内存，可能会出现内存不足导致分配失败的情况 | 按需分配内存，较为灵活 |
| 内存开销 | 除了存储数据本身，只需要少量额外的空间记录数组长度等信息 | 每个节点都需要额外的空间存储指针，内存开销相对较大 |
| 适用场景 | 适合频繁随机访问，元素数量相对固定的场景 | 适合频繁插入、删除操作，元素数量动态变化较大的场景 |
链表结构
设计链表
设计链表包含这些关键元素：链表节点（值和next指针）、初始化构造函数、访问、插入、删除、遍历方法。
测试通过代码：
#include<iostream>
class MyLinkedList {
public:
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode() : val(0), next(nullptr) {};
LinkedNode(int _val) :val(_val), next(nullptr) {};
};
MyLinkedList() {
this->_dummyHead = new LinkedNode();
this->_size = 0;
}
int get(int index) {
if (index < 0 || index > _size - 1) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index < 0 || index > _size) {
return;
}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
std::cout <<"index = " << index << "cur->val = " << cur->val<<std::endl;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index > _size - 1) {
return;
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
cur->next = cur->next->next;
_size--;
}
void printLinkedList() {
LinkedNode* cur = _dummyHead->next;
while (cur) {
std::cout << cur->val << " ";
cur = cur->next;
}
std::cout << std::endl;
std::cout << "size:" << _size << std::endl;
}
private:
LinkedNode* _dummyHead;
int _size;
};
常见链表结构
除了单链表外，还有两种常见的链表类型：
- 环形链表：链表的尾节点指向它的头节点，即可得到一个环形链表；在环形链表中，任意节点都可以被视为头节点；
- 双向链表：不同于单链表，双向链表中还放有它前驱节点的pre指针，其遍历灵活性更强，但占用空间也更多。
常考题型
链表成环
力扣：142. 环形链表 II - 力扣（LeetCode）
难度：中等
考察重点
- 确认链表是否成环；
- 快指针追上慢指针的原理；
- 找到链表环的入口；
- 寻找入口过程中三个指针走过的路程涉及的数学关系。
合并链表
力扣：21. 合并两个有序链表 - 力扣（LeetCode）
难度：简单
考察重点
- 双指针；
- 虚拟头节点；
- 递归或迭代。