Title Description:
Design the implementation of linked list. You can choose to use single linked list or double linked list. A node in a single linked list should have two attributes: val and next. val is the value of the current node, and next is the pointer / reference to the next node. If you want to use a two-way linked list, you also need an attribute prev to indicate the previous node in the linked list. It is assumed that all nodes in the linked list are 0-index.

Implement these functions in the linked list class:

get(index): get the value of the index node in the linked list. Returns - 1 if the index is invalid.
addAtHead(val): add a node with value val before the first element of the linked list. After insertion, the new node will become the first node in the linked list.
addAtTail(val): append the node with value val to the last element of the linked list.
addAtIndex(index,val): add a node with value val before the index node in the linked list. If the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. If the index is less than 0, the node is inserted in the header.
Delete atindex (index): if the index is valid, delete the index node in the linked list.

Example:

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); // The linked list becomes 1 - > 2 - > 3
linkedList.get(1); // Return 2
linkedList.deleteAtIndex(1); // Now the linked list is 1 - > 3
linkedList.get(1); // Return 3

Tips:

All val values are within [1, 1000].
The number of operations will be within [1, 1000].
Do not use the built-in LinkedList library.

Algorithm:

• First, the structure defines the Node and initializes it with the constructor initial value list; That is, Node(int val):val(val),next(nullptr) {}. The parameter is integer Val, representing the value of the Node; The initial value of the Node is Val, and the next is initialized to nullptr.
• Use m_size = 0;m_head = new Node(0); To initialize the size and header of the linked list. Use private at the end to define m_size and m_head, according to the scope of use of private, they can be used in similar member functions. That is, addAtHead(),addAtTail(), and other functions.
• Several member functions pay attention to the requirements of the topic. It is commonly used to move the working pointer to the position of the current operation.
  For example, when using index index, use while (index --) curnode = curnode - > next
  When the current node is empty, use while (curnode - > next! = null) curnode = curnode - > next;
• It is worth noting that addAtIndex(index,val) if the index is equal to the length of the linked list, the node will be attached to the end of the linked list. If the index is greater than the length of the linked list, the node will not be inserted. This situation also needs to be operated when it is equal to the length of the linked list. The general case where index does not conform to the index is index > M_ Size - 1 | index < 0. It must be distinguished here. If index > m is still used in addAtIndex function_ Size - 1, there will be general use cases that cannot pass.

class MyLinkedList {
public:
    /** Initialize your data structure here. */
    struct Node{
        int val;
        Node* next;
        Node(int val):val(val),next(nullptr){}
    };
    MyLinkedList() {
        m_size = 0;
        m_head = new Node(0);
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    int get(int index) {
        if(index>m_size - 1||index<0) return -1;
        Node *curNode = m_head->next;//here!!! The working pointer is next
        while(index--) curNode = curNode ->next;
        return curNode -> val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    void addAtHead(int val) {
        Node *newNode = new Node(val);
        newNode ->next = m_head->next;
        m_head->next = newNode;
        m_size++;
    }
    
    /** Append a node of value val to the last element of the linked list. */
    void addAtTail(int val) {
        Node* newNode = new Node(val);
        Node* curNode = m_head;
        while(curNode->next!=NULL) curNode = curNode->next;
        curNode->next = newNode;
        newNode->next = NULL;
        m_size ++;
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    void addAtIndex(int index, int val) {
        if(index>m_size) return;
        Node* newNode = new Node(val);
        Node* curNode = m_head;
        while(index--) curNode = curNode->next;
        newNode->next = curNode->next;
        curNode->next = newNode;
        m_size ++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    void deleteAtIndex(int index) {
        if(index>m_size - 1||index<0) return;
        Node* curNode = m_head;
        while(index--) curNode = curNode->next;
        Node* tmp = curNode->next;
        curNode->next = curNode->next->next;
        delete tmp;
        m_size--;
    }
    private:
        int m_size;
        Node *m_head;
};

/**
 * 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);
 */

Perfect finish~
reference resources:
707. Design linked list