题解 | 设计LRU缓存结构

class Solution {
public:
    struct ListNode {
        int key, val;
        ListNode *prev, *next;

        ListNode() : key(0), val(0), prev(nullptr), next(nullptr) {}
        ListNode(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {}
        ListNode(int key, int val, ListNode* prev, ListNode* next) : key(key), val(val), prev(prev), next(next) {}
    }*L, *R;
    unordered_map<int, ListNode*> hash;
    int n;

    Solution(int capacity) {
        // write code here
        n = capacity;
        L = new ListNode(-1, -1), R = new ListNode(-1, -1);
        L->next = R, R->prev = L;
    }

    void remove(ListNode *p) {
        p->next->prev = p->prev;
        p->prev->next = p->next;
    }

    void insert(ListNode *p) {
        p->next = L->next;
        p->prev = L;
        L->next->prev = p;
        L->next = p;
    }

    int get(int key) {
        // write code here
        if (hash.count(key) == 0) return -1;
        ListNode *p = hash[key];
        remove(p);
        insert(p);
        return p->val;
    }

    void set(int key, int value) {
        // write code here
        if (hash.count(key)) {
            ListNode *p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        } else {
            if (hash.size() == n) {
                ListNode *p = R->prev;
                remove(p);
                hash.erase(p->key);
                delete p;
            }
            ListNode *p = new ListNode(key, value);
            hash[key] = p;
            insert(p);
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* solution = new Solution(capacity);
 * int output = solution->get(key);
 * solution->set(key,value);
 */