C++ | 双向链表+哈希

维护一个双向链表，来记录LRU序列
将最近使用的放在头部，最末使用的放在尾部
通过一个 Node* back 指针标记优先级最低的键值对
使用哈希实现键值对快速查找，并更新节点到头部

链表节点更新，容易出各种问题，很考验个人的编码经验
这边从读题到写出来用来是用了29min(考试模式-不提示错误用例)
emmmmmm 感觉有点慢了...

class Solution {
private:
    struct Node{
        int key;
        int value;
        Node* last;
        Node* next;
    };

    Node* creatNode(int key,int value) {
        Node* nnod = new Node;
        nnod->key = key;
        nnod->value = value;
        nnod->next = nullptr;
        nnod->last = nullptr;
        return nnod;
    }

    Node head;
    int nl;
    int lm;
    Node* back;//尾部

    unordered_map<int,Node*> keymp;

public:


    Solution() {
        nl=0;
        head.next = nullptr;
        head.last = nullptr;
        back = nullptr;
    }

    void addKeyValue(int key,int value) {
        Node* temp;
        if(++nl>lm) { //需要除掉末尾节点
            nl = lm;
            keymp.erase(back->key);
            back->last->next = nullptr;
            temp = back->last;
            delete back;
            back = temp;
        }

        temp = creatNode(key,value);
        temp->last = &head;
        temp->next = head.next;
        if(head.next) head.next->last = temp;
        head.next = temp;
        if(!back) back = temp;

        keymp[key] = temp;

    }

    void getKey(int key,vector<int> & res) {
        if(keymp.count(key)) {
            Node* knod = keymp[key];
            res.emplace_back(knod->value);
            if(knod==head.next) return;//查找到头部无需更新
            if(knod!=back) {//查找到中间
                knod->last->next = knod->next;
                knod->next->last = knod->last;
            }else { //查找到back
                knod->last->next = nullptr;
                back = knod->last;
            }
            knod->last = &head;
            head.next->last = knod;
            knod->next = head.next;
            head.next = knod;

        }else {
            res.emplace_back(-1);
        }
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;
        lm = k;
        for(auto op : operators) {
            if(op[0]==1) {
                addKeyValue(op[1],op[2]);
            }else if(op[0]==2) {
                getKey(op[1],res);
            }
        }

        return res;
    }
};