707 设计链表——dummyHead好用

我算是知道dummyHead虚假头节点的妙处了，addAtHead的时候，不用判断链表是否为空，直接把新节点往dummyHead后面一连就可以

注意链表的长度要实时更新！

class MyLinkedList {
private:
    ListNode* _dummyHead;
    int _size;
public:
    //创建一个空链表，把成员变量初始化一下
    MyLinkedList() {
        _dummyHead = new ListNode(0);
        _size = 0;//链表的长度记得要实时更新！
    }
    
    int get(int index) {
        if((index < 0) || (index >= _size)) return -1;
        ListNode* cur = _dummyHead;
        //假设索引为3，dum 0 1 2 3，要找4次，cur成为我们要的节点
        for(int i = 0; i <= index; i++) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;//增加节点，链表长度更新
    }
    
    void addAtTail(int val) {
        ListNode* cur = _dummyHead;
        while(cur->next != nullptr) {
            cur = cur->next;
        }
        ListNode* newNode = new ListNode(val);
        cur->next = newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        else if(index == _size) {
            addAtTail(val); return;
        }
        else if(index == 0) {
            addAtHead(val); return;
        } else {
            ListNode* cur = _dummyHead;
            while(index--) {
                cur = cur->next;
            }
            ListNode* newNode = new ListNode(val);
            newNode->next = cur->next;
            cur->next = newNode;
            _size++;
        }
    }
    
    void deleteAtIndex(int index) {
        if((index < 0) || (index >= _size)) return;
        ListNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        ListNode* tem = cur->next;
        cur->next = cur->next->next;
        delete tem;
        _size--;
    }
};
 
/**
 * 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);
 */