题解 | #设计LRU缓存结构#

1个双向链表保存数据，一个map来保存链表指针，看起来挺简单的。但是有一个测试用例没过，不知道为啥？尴尬。。。。

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    struct LRUNode{
        int key;
        int val;
        struct LRUNode *next;
        struct LRUNode *pre;
        
        LRUNode(int key,int val){
            this->key = key;
            this->val = val;
        }
    };
    
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> res;
        //key and val
        unordered_map<int, LRUNode *> key_to_point;
        LRUNode *root = new LRUNode(0,0);
        LRUNode *tail = root;
        int len = 0;
        for(int i=0;i<operators.size();i++){
            int opt = operators[i][0];
            int key = operators[i][1];
            if(opt == 1){
                int val = operators[i][2];
                if(key_to_point.find(key) == key_to_point.end()){
                    if(len >= k){
                       int key1 = RemoveFirstNode(root);
                       LRUNode *fp =key_to_point[key1];
                       key_to_point.erase(key1);
                       free(fp);
                    }else{
                        len += 1;
                    }
                    
                    LRUNode *node = new LRUNode(key,val);
                    key_to_point[key] = node;
                    AddNode(tail, node);
                    tail = node;
                }else{
                    LRUNode *node = key_to_point[key];
                    node->val = val;
                    if(tail != node){
                        SwapToTail(tail,node);
                        tail = node;
                    }
                }
            }else{
                if(key_to_point.find(key) == key_to_point.end()){
                    res.push_back(-1);
                }else{
                    LRUNode *node = key_to_point[key];
                    if(tail != node){
                        SwapToTail(tail,node);
                        tail = node;
                    }
                    res.push_back(node->val);
                }
            }
        }
        return res;
    }
    
    void AddNode(LRUNode *tail,LRUNode *newNode){
        tail->next = newNode;
        newNode->pre = tail;
        newNode->next = NULL;
    }
    
    void SwapToTail(LRUNode *tail,LRUNode *node){
        LRUNode *preNode = node->pre;
        LRUNode *nextNode = node->next;
        node->pre = NULL;
        node->next = NULL;
        preNode->next = nextNode;
        nextNode->pre = preNode;
        tail->next = node;
    }
    
    int RemoveFirstNode(LRUNode *root){
        int res = -1;
        if(root->next == NULL){
            return res;
        }    
        
        LRUNode *firstNode = root->next;
        LRUNode *SecondNode = firstNode->next;
        root->next = SecondNode;
        if(SecondNode != NULL){
            SecondNode->pre = root;
        }
        res = firstNode->key;
        firstNode->pre = NULL;
        firstNode->next = NULL;
        return res;
    }
};