代码随想录第七天

链表-设计链表

题目链接

体验一下c和c++的不同

class MyLinkedList {
public:
    struct LinkedNode{
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val),next(nullptr){}
    };
    MyLinkedList() {
        myhead = new LinkedNode(0);
        size = 0;
    }
    
    int get(int index) {
        if(index >(size-1) || index < 0)return -1;
        LinkedNode* cur = myhead->next;
        while(index--)cur = cur->next;
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = myhead->next;
        myhead->next = newNode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode *tmp = myhead;
        while(tmp->next != nullptr)tmp = tmp->next;
        tmp->next = newNode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size) return;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode *tmp = myhead;

        while(index--) tmp = tmp->next;
        newNode->next = tmp->next;
        tmp->next = newNode;
        size++;
       
    }
    
    void deleteAtIndex(int index) {
        if (index >= size || index < 0) return;
        LinkedNode *cur = myhead;
        while(index--) cur = cur->next;
        LinkedNode *tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
 
    }
    void printLinkedList(){
        LinkedNode* cur = myhead;
        while(cur->next != nullptr){
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int size;
    LinkedNode* myhead;
};

/**
 * 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);
 */

typedef struct {
    int val;
    struct MyLinkedList* next;
} MyLinkedList;


MyLinkedList* myLinkedListCreate() {
    MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    head->next = NULL;
    return head;
}

int myLinkedListGet(MyLinkedList* obj, int index) {
    MyLinkedList* cur = obj->next;
    for(int i = 0; cur != NULL; i++){
        if(i == index)
            return cur->val;
        else
            cur = cur->next;

    }
    return -1;
}

void myLinkedListAddAtHead(MyLinkedList* obj, int val) {
    MyLinkedList* cur = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    cur->val = val;
    cur->next = obj->next;
    obj->next = cur;
}

void myLinkedListAddAtTail(MyLinkedList* obj, int val) {
    MyLinkedList* cur = obj;
    MyLinkedList* tHead = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    tHead->val = val;
    tHead->next = NULL;
    while(cur->next != NULL)
        cur = cur->next;
    cur->next = tHead;
}

void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) {
    if(index == 0){
        myLinkedListAddAtHead(obj, val);
        return;
    }

    MyLinkedList* nhead = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    nhead->val = val;
    MyLinkedList* cur = obj->next;

    for(int i = 1; cur != NULL; i++){
        if(i == index){
            nhead->next = cur->next;
            cur->next = nhead;
            return;
        }
        else
            cur = cur->next;
    }
}

void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) {
    if(index == 0){
        MyLinkedList *tmp = obj->next;
        if (tmp != NULL){
            obj->next = tmp->next;
            free(tmp);   
        }
        return;
    }
    MyLinkedList *cur = obj->next;
    for (int i = 1 ;cur != NULL && cur->next != NULL; i++){
        if (i == index){
            MyLinkedList *tmp = cur->next;
            if (tmp != NULL) {
                cur->next = tmp->next;
                free(tmp);
            }
            return;
        }
        else{
            cur = cur->next;
        }
    }
}

void myLinkedListFree(MyLinkedList* obj) {
        while(obj != NULL){
        MyLinkedList *tmp = obj;
        obj = obj->next;
        free(tmp);
    }
}

/**
 * Your MyLinkedList struct will be instantiated and called as such:
 * MyLinkedList* obj = myLinkedListCreate();
 * int param_1 = myLinkedListGet(obj, index);
 
 * myLinkedListAddAtHead(obj, val);
 
 * myLinkedListAddAtTail(obj, val);
 
 * myLinkedListAddAtIndex(obj, index, val);
 
 * myLinkedListDeleteAtIndex(obj, index);
 
 * myLinkedListFree(obj);
*/