關(guān)于鏈表获三，做一些增刪查改操作，常用套路有兩個(gè)：
1.增加虛擬頭節(jié)點(diǎn)退盯；
2.快奄喂、慢指針

203. 移除鏈表元素

非遞歸做法

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode *cur = dummyHead;
        while(cur->next !=nullptr) {
            if (cur->next->val == val) {
                ListNode *temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

注意點(diǎn)

1、增加虛擬頭節(jié)點(diǎn)绵脯，這樣就不用特地針對(duì)頭節(jié)點(diǎn)做特殊處理佳励。譬如head為空的情況或者只有一個(gè)頭節(jié)點(diǎn)的情況
2、刪除節(jié)點(diǎn)后桨嫁，記得delete操作植兰，防止內(nèi)存泄漏

206. 反轉(zhuǎn)鏈表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;
        while (cur != nullptr) {
            ListNode *temp = cur;
            cur = cur->next;
            temp->next = pre;
            pre = temp;
        }
        return pre;
    }
};

關(guān)鍵點(diǎn)：畫清楚反轉(zhuǎn)過(guò)程就ok了

707. 設(shè)計(jì)鏈表

class MyLinkedList {
public:
    // 定義鏈表節(jié)點(diǎn)結(jié)構(gòu)體
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    // 初始化鏈表
    MyLinkedList() {
        _dummyHead = new LinkedNode(0); // 這里定義的頭結(jié)點(diǎn) 是一個(gè)虛擬頭結(jié)點(diǎn)，而不是真正的鏈表頭結(jié)點(diǎn)
        _size = 0;
    }

    // 獲取到第index個(gè)節(jié)點(diǎn)數(shù)值璃吧，如果index是非法數(shù)值直接返回-1楣导， 注意index是從0開始的，第0個(gè)節(jié)點(diǎn)就是頭結(jié)點(diǎn)
    int get(int index) {
        if (index > (_size - 1) || index < 0) {
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){ // 如果--index 就會(huì)陷入死循環(huán)
            cur = cur->next;
        }
        return cur->val;
    }

    // 在鏈表最前面插入一個(gè)節(jié)點(diǎn)畜挨，插入完成后筒繁，新插入的節(jié)點(diǎn)為鏈表的新的頭結(jié)點(diǎn)
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        _size++;
    }

    // 在鏈表最后面添加一個(gè)節(jié)點(diǎn)
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next != nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }

    // 在第index個(gè)節(jié)點(diǎn)之前插入一個(gè)新節(jié)點(diǎn)噩凹，例如index為0，那么新插入的節(jié)點(diǎn)為鏈表的新頭節(jié)點(diǎn)毡咏。
    // 如果index 等于鏈表的長(zhǎng)度驮宴，則說(shuō)明是新插入的節(jié)點(diǎn)為鏈表的尾結(jié)點(diǎn)
    // 如果index大于鏈表的長(zhǎng)度，則返回空
    void addAtIndex(int index, int val) {
        if (index > _size) {
            return;
        }
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }

    // 刪除第index個(gè)節(jié)點(diǎn)呕缭，如果index 大于等于鏈表的長(zhǎng)度堵泽，直接return，注意index是從0開始的
    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--) {
            cur = cur ->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        _size--;
    }

    // 打印鏈表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;

};