1、单链表

我们可以自定义ListNode类型，值得注意的是，考虑到我们需要先声明后定义，故先声明public，再声明private。对于MyLinkedList，我们需要保存链表的虚拟头节点以及其长度用于遍历链表。其中插入删除的操作需要注意前后指针的指向。

值得注意的是，我们使用new定义新的ListNode对象，这样能够确保返回的是对象指针。

class MyLinkedList {
public:struct ListNode {int val;ListNode *next;ListNode(int val) : val(val), next(nullptr) {}};MyLinkedList() {head = new ListNode(0);length = 0;}int get(int index) {if (index < 0 || index >= length) {return -1;}ListNode *cur = head->next;for (int i = 0; i < index; ++i) {cur = cur->next;}return cur->val;}void addAtHead(int val) {ListNode *temp = new ListNode(val);temp->next = head->next;head->next = temp;++length;}void addAtTail(int val) {ListNode *cur = head;while (cur->next != nullptr) {cur = cur->next;}ListNode *temp = new ListNode(val);cur->next = temp;++length;}void addAtIndex(int index, int val) {if (index > length) {return;}ListNode *cur = head;for (int i = 0; i < index; ++i) {cur = cur->next;}ListNode *temp = new ListNode(val);temp->next = cur->next;cur->next = temp;++length;}void deleteAtIndex(int index) {if (index >= length || index < 0) {return;}ListNode *cur = head;for (int i = 0; i < index; ++i) {cur = cur->next;}cur->next = cur->next->next;--length;}private:ListNode *head;int length;
};