146 LRU缓存

解题思路：
\qquad 题目要求get()和put()要有O(1)时间复杂度。
\qquad get()可以利用Map，实现O(1)内<key, value>的快速查找;
\qquad 如何选择合适的数据结构，将访问过的<key, value>的优先级在O(1)内提高呢？首先，这个数据结构要是有序的，且它任意元素的删除和插入要在O(1)复杂度内完成。因此排除数组、队列、堆栈等，剩下链表作为一个不错的选择。
\qquad 现在，我们可以通过map快速定义到，待更新元素的位置。但要将链表中的元素删除，需要知道上一个节点才行，因此我们的链表不能是单向的，而是双向的。到此，我们知道使用 Map+双向链表的形式就可以解决这道题了。

\qquad 代码实现中，记得将双向链表元素删除、插入封装成函数，可以使代码更精简一些。

struct ListNode
    {
        int key;
        int value;
        ListNode* prev;
        ListNode* next;
        ListNode() : key(0), value(0), prev(nullptr), next(nullptr){}
        ListNode(int x, int y): key(x), value(y), prev(nullptr), next(nullptr){}
    };
    int size = 0;
    unordered_map<int, ListNode*> m;
    ListNode* head;
    ListNode* end;

    LRUCache(int capacity) {
        size = capacity;
        m.clear();
        head = new ListNode(-1, -1);
        end  = new ListNode(-1, -1);
        head->next = end;
        end->prev = head;
    }
    
    int get(int key) {
        if(m.count(key) == 0) return -1;
        removeNode(m[key]);
        addToEnd(m[key]);
        return m[key]->value;
    }
    
    void put(int key, int value) {
       if(m.count(key) == 0) m[key] = new ListNode(key, value);
       else
       {
            m[key]->value = value;
            removeNode(m[key]);
       }
       addToEnd(m[key]);
       if(m.size() > size)
       {
            m.erase(head->next->key);
            removeNode(head->next);
       }
    }

    void removeNode(ListNode* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToEnd(ListNode* node)
    {
        node->prev = end->prev;
        node->next = end;
        end->prev->next = node;
        end->prev = node;
    }