2.2 linked list - Design linked list (leetcode 707)

Leetcode 707

class MyLinkedList {
    
public:

    //  Define linked list node structure 
    struct ListNode {
    
        int val;
        ListNode* next;
        ListNode(): val(0), next(nullptr) {
    }
        ListNode(int x): val(x), next(nullptr) {
    }
        ListNode(int x, ListNode* next): val(x), next(next) {
    }
    };

    //  Constructors 
    MyLinkedList() {
    
        _dummyHead = new ListNode(0);//  The head node defined here   It's a virtual head node , Instead of the real chain header node 
        _size = 0;
    }
    

    
    //  Get to page No index Node values , If index It's illegal. It's returned directly -1,  Be careful index It's from 0 At the beginning , The first 0 The first node is the head node 
    int get(int index) {
    
        if(index > (_size-1) || index < 0){
       //  illegal value （_size To calculate the dummyHead, Therefore need -1）
            return -1;
        }

        ListNode* cur = _dummyHead->next; //  Initialize as the head node 
        while(index--){
    
            cur = cur->next;
        }

        return cur->val;
    }
    
    //  Insert a node at the front of the linked list , After insertion , The newly inserted node is the new head node of the linked list 
    void addAtHead(int val) {
    
        ListNode* newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }
    
    //  Add a node to the last side of the list 
    void addAtTail(int val) {
    
        ListNode* newNode = new ListNode(val);
        ListNode* cur = _dummyHead;  //  Notice that this is _dummyHead

        while(cur->next != nullptr){
    
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    

    //  In the list, the  index  The value added before nodes is  val  The node of .
    // 1.  If  index  It's equal to the length of the list , Then the node will be attached to the end of the list .
    // 2.  If  index  Greater than the length of the list , The node will not be inserted .
    // 3.  If  index  Less than 0, Then insert the node in the head .
    void addAtIndex(int index, int val) {
    
        if(index > _size){
      
            return ;
        }

        ListNode* newNode = new ListNode(val);
        ListNode* cur = _dummyHead; //  Notice that this is _dummyHead
        while(index--){
    
            cur = cur->next;
        }
        newNode->next = cur->next; //  Pay attention to the connection sequence 
        cur->next = newNode;
        _size++;

    }
    
    //  If the index  index  It works , Delete the  index  Nodes 
    void deleteAtIndex(int index) {
    
        if(index >= _size || index < 0){
      
            return ;
        }

        ListNode* cur = _dummyHead; //  Notice that this is _dummyHead
        while(index--){
    
            cur = cur->next;
        }
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;

    }

private:
    int _size ;
    ListNode* _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); */