目录
题意速览
设计一个支持如下操作的链表：
get(index)：返回索引index处的值，不合法返回-1；addAtHead(val)：头插；addAtTail(val)：尾插；addAtIndex(index, val)：在index位置前插入；如果index==size等价尾插；如果index>size不插；如果index<0按头插处理；deleteAtIndex(index)：删除index处节点，非法索引则忽略。
解题思路与设计要点
- 使用「虚拟头结点 DummyHead」简化边界：头插、删头都不用特判。
- 维护
size保证O(1)判合法与尾插定位边界； - 单链表前驱节点访问需要遍历，统一封装「定位到 index 的前一节点」的辅助函数；
addAtIndex对index<0视为0（题目要求），对index>size直接 return；deleteAtIndex需校验范围[0, size-1]。
C++ 代码实现（单链表 + 虚拟头结点）
#include <bits/stdc++.h>
using namespace std;
class MyLinkedList {
public:
struct Node {
int val; Node* next;
Node(int v=0): val(v), next(nullptr) {}
};
MyLinkedList() {
_dummy = new Node(); // 虚拟头
_size = 0;
}
int get(int index) {
if (index < 0 || index >= _size) return -1;
Node* cur = _dummy->next;
while (index--) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
addAtIndex(0, val);
}
void addAtTail(int val) {
addAtIndex(_size, val);
}
void addAtIndex(int index, int val) {
if (index > _size) return; // 超界不插
if (index < 0) index = 0; // 负数按 0 处理
Node* prev = _dummy;
for (int i = 0; i < index; ++i) prev = prev->next;
Node* node = new Node(val);
node->next = prev->next;
prev->next = node;
++_size;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= _size) return;
Node* prev = _dummy;
for (int i = 0; i < index; ++i) prev = prev->next;
Node* del = prev->next;
prev->next = del->next;
delete del;
--_size;
}
~MyLinkedList() {
Node* cur = _dummy;
while (cur) { Node* nxt = cur->next; delete cur; cur = nxt; }
}
private:
Node* _dummy;
int _size;
};
时间复杂度与空间复杂度
get / addAtIndex / deleteAtIndex定位需要 O(n)；addAtHead / addAtTail退化到 O(n)（单链表无尾指针情况下），如需 O(1) 尾插可维护尾指针；- 额外空间 O(1)（不计存储本身）。
常见坑位与边界用例
index == size允许插入（等价尾插）；index > size直接忽略。index < 0视为头插；- 先移动到前驱位置再插/删，避免对
index==0的特判； - 删除后别忘
--size，插入后++size； - 析构释放所有节点（在线评测不强制，但工程上必须）。
推荐用例（覆盖边界）：
addAtHead(1) -> [1]
addAtTail(3) -> [1,3]
addAtIndex(1,2) -> [1,2,3]
get(1) == 2
deleteAtIndex(1) -> [1,3]
get(1) == 3
addAtIndex(5,10) -> ignore
addAtIndex(-2,7) -> [7,1,3]
对比：双链表如何优化
- 额外存
prev指针，可O(1)从任意节点删除； - 若同时维护尾指针与 size，
addAtTail可达O(1)； - 但节点更重，内存与指针安全性要求更高（注意野指针/悬垂指针）。
单元测试样例（可直接粘贴运行）
#include <bits/stdc++.h>
using namespace std;
// 将上面的 MyLinkedList 粘贴到此处
int main() {
MyLinkedList list;
list.addAtHead(1);
list.addAtTail(3);
list.addAtIndex(1, 2); // [1,2,3]
cout << list.get(1) << "\n"; // 2
list.deleteAtIndex(1); // [1,3]
cout << list.get(1) << "\n"; // 3
list.addAtIndex(5, 10); // ignore
list.addAtIndex(-2, 7); // [7,1,3]
cout << list.get(0) << "," << list.get(1) << "," << list.get(2) << "\n"; // 7,1,3
return 0;
}
总结
- 这题的本质是「抽象一个受控的链表 API」，工程感强：
- 统一用 Dummy Head 吸收边界。
- 明确
index规则并维护size。 - 写完先过“增删改查 + 异常输入”的自测清单。
- 若要进一步提速，可切到双链表并维护尾指针；如对内存敏感或题目简单，单链表足够。