[数据结构与算法]LeetCode 707. 设计链表

题目比较唬人，细心一点还是能做出来的

单链表。头节点不存放数据

class MyLinkedList {
public:
    struct node{
        int val;
        node* next;
        node(int val):val(val),next(NULL){}
    };

    MyLinkedList() {
        head = new node(0);
        count = 0;
    }
    
    int get(int index) {
        if(index >= count || index < 0)
            return -1;
        node* p = head->next;
        for(int i = 0; i < index; i++)
            p = p->next;
        return p->val;
    }
    
    void addAtHead(int val) {
        node* p = new node(val);
        p->next = head->next;
        head->next = p;
        count++;
    }
    
    void addAtTail(int val) {
        node* p = head;
        for(int i = 0; i < count; i++)
            p = p->next;
        p->next = new node(val);
        count++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > count || index < 0)
            return;
        if(index == count)  //之前  
        {
            addAtTail(val);
            return;
        }
        node* p = head;
        for(int i = 0; i < index; i++)
        {
            p = p->next;
        }
        node* en = new node(val);
        en->next = p->next;
        p->next = en;
        count++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= count)
            return;
        node* p = head;
        for(int i = 0; i < index; i++)
        {
            p = p->next;
        }
        p->next = p->next->next;
        count--;
    }

private:
    node* head;
    int count;

};

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

在单链表基础上改的双链表

class MyLinkedList {
public:
    struct node{
        int val;
        node* next;
        node* prev;
        node(int val):val(val),next(NULL),prev(NULL){}
    };

    MyLinkedList() {
        head = new node(0);
        count = 0;
    }
    
    int get(int index) {
        if(index >= count || index < 0)
            return -1;
        node* p = head->next;
        for(int i = 0; i < index; i++)
            p = p->next;
        return p->val;
    }
    
    void addAtHead(int val) {
        node* p = new node(val);
        p->next = head->next;
        p->prev = head;
        if(count != 0)
            p->next->prev = p;
        head->next = p;
        count++;
    }
    
    void addAtTail(int val) {
        node* p = head;
        for(int i = 0; i < count; i++)
            p = p->next;
        p->next = new node(val);
        p->next->prev = p;
        count++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > count || index < 0)
            return;
        if(index == count)  //之前  
        {
            addAtTail(val);
            return;
        }
        node* p = head;
        for(int i = 0; i < index; i++)
        {
            p = p->next;
        }
        node* en = new node(val);
        p->next->prev = en;
        en->next = p->next;
        p->next = en;
        en->prev = p;
        count++;
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= count)
            return;
        node* p = head;
        for(int i = 0; i < index; i++)
        {
            p = p->next;
        }
        p->next = p->next->next;
        if(p->next != NULL)
            p->next->prev = p;
        count--;
    }

private:
    node* head;
    int count;

};

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