119.设计链表（力扣）

代码解决 

class MyLinkedList {
public:
 
   // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
 
    MyLinkedList() {
        dummyhead =new LinkedNode(0);
        size=0;
    }
    
    int get(int index) {
        if (index > (size - 1) || index < 0) {
            return -1;
        }
        LinkedNode*node=dummyhead->next;
        while(index){
            node=node->next;
            index--;
        }
        return node->val;
    }
    
    void addAtHead(int val) {
        LinkedNode*node=new LinkedNode(val);
        node->next=dummyhead->next;
        dummyhead->next=node;
        size++;
 
    }
    
    void addAtTail(int val) {
        LinkedNode*node=new LinkedNode(val);
        LinkedNode*cur=dummyhead;
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        node->next=cur->next;
        cur->next=node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size) return;
        if(index < 0) index = 0;        
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyhead;
        while(index){
            cur=cur->next;
            index--;
        }
        newNode->next=cur->next;
        cur->next=newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        LinkedNode* newNode = dummyhead;
        LinkedNode* cur = dummyhead;
        while(index){
            cur=cur->next;
            index--;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
 
        tmp=nullptr;
        size--;
    }
private:
    int size;
    LinkedNode* dummyhead;
 
};
 
/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

实现思路

当创建一个 MyLinkedList 对象时，它会初始化一个虚拟头节点 dummyhead，并将链表的大小 size 初始化为 0。链表的每个节点都包含一个整数值 val 和一个指向下一个节点的指针 next。

1. 添加节点：

• addAtHead(int val) 方法会在链表头部插入一个新节点。它创建一个新的节点，将新节点的 next 指向当前头节点，然后更新 dummyhead 的 next 指针为新节点，并增加链表的大小 size。

• addAtTail(int val) 方法会在链表尾部插入一个新节点。它遍历链表直到最后一个节点，然后将新节点插入到最后一个节点的后面，并增加链表的大小 size。

• addAtIndex(int index, int val) 方法会在指定索引处插入一个新节点。它遍历链表直到达到指定索引的前一个节点，然后将新节点插入到前一个节点的后面，并增加链表的大小 size。

2. 获取节点：

• get(int index) 方法会获取指定索引处节点的值。它遍历链表直到达到指定索引的节点，并返回该节点的值。

3. 删除节点：

• deleteAtIndex(int index) 方法会删除指定索引处的节点。它遍历链表直到达到指定索引的前一个节点，然后将前一个节点的 next 指针指向要删除节点的下一个节点，并释放被删除节点的内存，最后减少链表的大小 size。