leetcode

707. 设计链表

力扣题目链接

// struct ListNode{
//     int val;
//     ListNode* next;
//     ListNode():val(0), next(NULL){}
//     ListNode(int x): val(x), next(NULL){}
//     ListNode(int x, ListNode*next):val(x), next(next){}
// };

class MyLinkedList {
public:
    int size;
    ListNode* dummyhead;

    MyLinkedList() {
        dummyhead = new ListNode(0);
        size = 0;
    }
    
    int get(int index) {
        if (index<0||index>=size) return -1;
        ListNode* current = dummyhead->next;
        while(index--) current = current->next;
        return current->val;
    }
    
    void addAtHead(int val) {
        ListNode*newnode = new ListNode(val);
        // 此题没有head, head = dummyhead->next
        newnode->next = dummyhead->next;
        dummyhead->next = newnode;
        size++;
    }
    
    void addAtTail(int val) {
        ListNode*newnode = new ListNode(val);
        ListNode* current = dummyhead;
        // 错误 while(size--){...}，会修改size值，可以while(sizecopy--){...}
        // 等价于while(current->next != NULL)
        while(current->next) current = current->next;
        current->next = newnode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        ListNode*newnode = new ListNode(val);
        ListNode*current = dummyhead;
        while(index--) current = current->next;
        newnode->next = current->next;
        current->next = newnode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index >= size || index <0) return;
        ListNode*current = dummyhead;
        while(index--) current =current->next;
        // 标记一下 current->next 之后才能删除内存
        ListNode*tmp = current->next;
        current->next = current->next->next;
        delete tmp;
        // delete删除tmp后tmp的值/地址是随机值，即乱指的悬挂指针（dangling pointer）。后面再用到tmp的话，指向难以预想的内存空间
        // 错误：delete指针后记得将指针的值设为NULL
        tmp = NULL;
        size--;
    }

    void printlinkedlist(){
        ListNode* current = dummyhead;
        while(current->next){
            current = current->next;
            std::cout << current->val << ' ';
        }
    }
};
// 野指针（wild pointer）指未初始化的指针，区别于悬挂指针

This site is open source. Improve this page.