设计链表

Leetcode题目链接

描述

详见中文题目链接。

解答

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

    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        _size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= _size) return -1;
        auto curr = dummyHead->next;
        while (index--) curr = curr->next;
        return curr->val;
    }

    void addAtHead(int val) {
        addAtIndex(0, val);
    }

    void addAtTail(int val) {
        addAtIndex(_size, val);
    }

    void addAtIndex(int index, int val) {
        if (index > _size) return;
        if (index < 0) index = 0;

        auto curr = dummyHead;
        while (index--) curr = curr->next;

        auto toAdd = new LinkedNode(val);
        toAdd->next = curr->next;
        curr->next = toAdd;

        _size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= _size) return;

        auto curr = dummyHead;
        while (index--) curr = curr->next;

        curr->next = curr->next->next;
        _size--;
    }
private:
    int _size;
    LinkedNode* dummyHead;
};

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