题目来源：. - 力扣（LeetCode）
题目思路分析
在编程中，链表是一种常见的数据结构，用于存储一系列元素，但与数组不同，链表中的元素在内存中不必连续存储。每个元素（称为节点）包含数据部分和一个指向下一个节点的指针。本题要求我们实现一个自定义的链表类MyLinkedList，支持以下操作：
- 获取指定位置的元素：
get(int index)方法，根据索引返回链表中的元素值，索引无效时返回-1。 - 在头部添加元素：
addAtHead(int val)方法，在链表头部插入一个新节点。 - 在尾部添加元素：
addAtTail(int val)方法，在链表尾部插入一个新节点。 - 在指定位置添加元素：
addAtIndex(int index, int val)方法，在链表的指定位置插入一个新节点。 - 删除指定位置的元素：
deleteAtIndex(int index)方法，删除链表中指定位置的节点。
为了高效实现这些操作，我们需要维护一个指向链表头部的指针（head），以及一个记录链表大小的变量（size）。使用虚拟头节点（dummy node）可以简化边界情况的处理，例如当index为0时，我们不需要特殊处理头部插入的情况。
代码实现与注解
实例：
#include <algorithm> // 为了使用std::max struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {}
}; class MyLinkedList {
public: MyLinkedList() { this->size = 0; // 使用虚拟头节点简化操作 this->head = new ListNode(0); } // 获取指定位置的元素值 int get(int index) { if (index < 0 || index >= size) { return -1; // 索引无效，返回-1 } ListNode *cur = head; for (int i = 0; i <= index; i++) { // 循环到目标位置的后一个节点 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; // 索引超出链表长度，不执行任何操作 } index = max(0, index); // 确保索引不小于0 size++; // 链表长度加1 ListNode *pred = head; for (int i = 0; i < index; i++) { pred = pred->next; } ListNode *add = new ListNode(val); add->next = pred->next; // 新节点的next指向原位置的下一个节点 pred->next = add; // 原位置的节点指向新节点 } // 删除指定位置的元素 void deleteAtIndex(int index) { if (index < 0 || index >= size) { return; // 索引无效，不执行任何操作 } size--; // 链表长度减1 ListNode *pred = head; for (int i = 0; i < index; i++) { pred = pred->next; } ListNode *p = pred->next; // 待删除节点 pred->next = pred->next->next; // 跳过待删除节点 delete p; // 释放待删除节点的内存 } private: int size; // 链表长度 ListNode *head; // 链表头部指针（虚拟头节点）
};主函数部分：
int main() { MyLinkedList* obj = new MyLinkedList(); obj->addAtHead(1); obj->addAtTail(3); obj->addAtIndex(1, 2); // 链表现在是1->2->3 cout << obj->get(1) << endl; // 输出2 obj->deleteAtIndex(1); // 删除索引1处的节点，链表现在是1->3 cout << obj->get(1) << endl; // 输出3 delete obj; return 0;
}
