目录

• 题意速览
• 解题思路与设计要点
• C++ 代码实现（单链表 + 虚拟头结点）
• 时间复杂度与空间复杂度
• 常见坑位与边界用例
• 对比：双链表如何优化
• 单元测试样例（可直接粘贴运行）
• 总结

---

题意速览

设计一个支持如下操作的链表：

• 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"; // 2list.deleteAtIndex(1);   // [1,3]cout << list.get(1) << "\n"; // 3list.addAtIndex(5, 10);  // ignorelist.addAtIndex(-2, 7);  // [7,1,3]cout << list.get(0) << "," << list.get(1) << "," << list.get(2) << "\n"; // 7,1,3return 0;
}

---

总结

• 这题的本质是「抽象一个受控的链表 API」，工程感强：
  • 统一用 Dummy Head 吸收边界。
  • 明确 index 规则并维护 size。
  • 写完先过“增删改查 + 异常输入”的自测清单。
• 若要进一步提速，可切到双链表并维护尾指针；如对内存敏感或题目简单，单链表足够。