#链表 #设计链表

design-linked-list.cpp

class MyLinkedList {
    struct Node {
        int val;
        struct Node* next;
        Node(): val(0), next(NULL) {}
        Node(int v): val(v), next(NULL) {}
    };

    Node* head_;
    int size_;
public:
    MyLinkedList() {
        head_ = new Node(0); // 虚拟头节点
        size_ = 0;
    }
    
    int get(int index) {
        if (index < 0 || index > size_ - 1) return -1;

        Node* tmp = head_->next; // 获取真实的头节点 
        for (int i = 0; i < index; ++i) {
            tmp = tmp->next;            
        }
        return tmp->val;
    }
    
    void addAtHead(int val) {
        Node* tmp = new Node(val);
        tmp->next = head_->next;
        head_->next = tmp;
        ++size_;
    }
    
    void addAtTail(int val) {
        Node* tmp = head_;
        while (tmp->next != NULL) {
            tmp = tmp->next;
        }
        tmp->next = new Node(val);
        ++size_;
    }
    
    void addAtIndex(int index, int val) {
        if (index > size_) return;

        Node* tmp = head_;
        for (int i = 0; i < index; ++i) {
            tmp = tmp->next;
        }
        Node* new_node = new Node(val);
        new_node->next = tmp->next;
        tmp->next = new_node;
        ++size_;
    }
    
    void deleteAtIndex(int index) {
        if (index < 0 || index >= size_) return;

        Node* tmp = head_;
        for (int i = 0; i < index; ++i) {
            tmp = tmp->next;
        }
        Node* to_delete = tmp->next;
        tmp->next = to_delete->next;
        delete to_delete;
        --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);
 */