立志重刷代码随想录60天冲冲冲！！——第三天

203. 移除链表元素

删除保存的节点，并赋空，养成好习惯

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 创建虚拟头节点
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* cur = dummyHead;
        while (cur->next != NULL) { //cur的next不为空
            if (cur->next->val == val) {
                cur->next = cur->next->next;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next; 
        delete dummyHead;  // 清空内存，养成好习惯
        return head;
    }
};

707. 设计链表

定义不熟练，需加强。

记得size全局变量

删除保存的节点，并赋空，养成好习惯

class MyLinkedList {
public:
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val): val(val), next(nullptr) {};
    };

    // 全局变量
    int size;
    LinkedNode* dummzyHead;

    MyLinkedList() {
        size = 0;
        dummzyHead = new LinkedNode(0);
    }
    
    int get(int index) {
        if (index < 0 || index > size - 1) {
            return -1;
        }
        LinkedNode* cur = dummzyHead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* cur = dummzyHead;
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* cur = dummzyHead;
        LinkedNode* newNode = new LinkedNode(val);
        while (cur->next != NULL) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index < 0 || index > size) { //需要满足index == size时，插入最后。size不用-1
            return;
        }

        LinkedNode* cur = dummzyHead;
        LinkedNode* newNode = new LinkedNode(val);
        while (index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1){return;}

        LinkedNode* cur = dummzyHead;
        while(index--) {
            cur = cur->next;
        }
        LinkedNode* tem = cur->next;
        cur->next = cur->next->next;
        
        delete tem;//删除保存的节点
        tem = nullptr;//给临时的节点赋空
        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);
 */

206. 反转链表

这个没啥好说的，双指针，反转，秒

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* cur = head;

        while (cur) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};