LRU：链表+双向链表

直接利用map写会超时......参考大佬意见后，用C++写出这个题解，虽然效率也不是很高，但，emmm，通过了

#include<unordered_map>
using namespace std;
struct NodeList {
        int key, val;
        NodeList* pre;
        NodeList* next;
        NodeList() {
            key = 0; val = 0;
            pre = nullptr;
            next = nullptr;
        }
        NodeList(int key1, int val1) {
            val = val1;
            key = key1;
            pre = nullptr;
            next = nullptr;
        }
};
class Solution {
private:
    unordered_map<int, NodeList* >Unmap;
    NodeList* head;
    NodeList* tail;
    int n = 0;
    int cap;
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> ans;
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code hereint i;
        if (k < 1)
            return {};
        this->cap = k;
        head = new NodeList();
        tail = new NodeList();
        head->next = tail;
        tail->pre = head;
        int m = operators.size();
        if (m == 0)
            return {};
        for (int i = 0; i < m; i++) {
            if (operators[i][0] == 1)
                put(operators[i][1], operators[i][2]);
            if (operators[i][0] == 2)
                get(operators[i][1]);
        }
        return ans;
    }
void Remove(NodeList* node) {//移除结点
    node->pre->next = node->next;
    node->next->pre = node->pre;
}
NodeList* RemoveTail() {//如果数据数目超过限定，移除尾结点的前驱结点
    NodeList* node = tail->pre;
    Remove(node);
    return node;
}
void AddToHead(NodeList* node) {//将新结点加到头节点之后
    node->next = head->next;
    head->next->pre = node;
    head->next = node;
    node->pre = head;
}
void MoveToHead(NodeList* node) {//将最近使用过的最新的结点移到头结点之后
    Remove(node);//将结点从原位置移除
    AddToHead(node);
}
void get(int key) {
    if (!Unmap.count(key))//如果不存在，则将-1放入ans中
        ans.push_back(-1);
    else {
        MoveToHead(Unmap[key]);//查找到则更新为最新的结点
        ans.push_back(Unmap[key]->val);
    }
}
void put(int key, int val1) {
    if (Unmap.find(key) != Unmap.end()) {//查找到，则将val值更改
        Unmap[key]->val = val1;
        MoveToHead(Unmap[key]);
    }
    else {
        NodeList* node = new NodeList(key, val1);
        Unmap[key] = node;
        AddToHead(node);
        n++;
    }
    if (n > cap) {//数据数目超过限制
        NodeList* removed = RemoveTail();
        Unmap.erase(removed->key);//将Unmap中的key值移除
        delete removed;
        n--;
    }
}
};