代码随想录day3

203:移除链表元素：注意虚拟头节点的使用

ListNode* removeElements(ListNode* head, int val) {
        ListNode* result = new ListNode();
        result->next = head;
        ListNode* current = result;
        while(current != nullptr && current->next != nullptr){
            if(current->next->val == val){
                ListNode* tmp = current->next;
                current->next = tmp->next;
                delete tmp;
            }else{
                current = current->next;
            }
        }
        return result->next;
    }

707.设计链表：依然采用虚拟头节点方式

todo:学习双指针写法

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

    };
    MyLinkedList() {
        prev = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index < 0 || index >= _size){
            return -1;
        }
        LinkedNode* current = prev->next;//注意此处起始位置
        while(index--){
            current = current->next;
        }
        return current->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* current = new LinkedNode(val);
        LinkedNode* tmp = prev->next;
        current->next = tmp;
        prev->next = current;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* current = prev;
        while(current->next != nullptr){
            current = current->next;
        }
        LinkedNode* tail = new LinkedNode(val);
        current->next = tail;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > _size){
            return;
        }
        if(index < 0) index = 0;
        
        LinkedNode* current = prev;
        while(index--){
            current = current->next;
        }
        LinkedNode* node = new LinkedNode(val);
        node->next = current->next;
        current->next = node;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index > _size-1){
            return;
        }
        LinkedNode* current = prev;
        while(index--){
            current = current->next;
        }
        LinkedNode* tmp = current->next;
        current->next = tmp->next;
        delete tmp;
        _size--;
    }
private:
    int _size;
    LinkedNode* prev;
};

206.反转链表：学习使用双链表法

ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* tmp = head;
        while(cur){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }