struct ListNode {
    int key, value;
    ListNode *prev, *next;
    ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

void removeNode(ListNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
<p>void addToHead(ListNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}</p>

#include <iostream>
#include <unordered_map>
using namespace std;
<p>class LRUCache {
private:
struct ListNode {
int key, value;
ListNode <em>prev, </em>next;
ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};</p><pre class='brush:php;toolbar:false;'>int capacity;
unordered_map<int, ListNode*> cache;
ListNode *head, *tail;

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

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

void moveToHead(ListNode* node) {
    removeNode(node);
    addToHead(node);
}

ListNode* popTail() {
    ListNode* last = tail->prev;
    removeNode(last);
    return last;
}

public: LRUCache(int cap) { capacity = cap; head = new ListNode(0, 0); tail = new ListNode(0, 0); head->next = tail; tail->prev = head; }

int get(int key) {
    if (cache.find(key) == cache.end()) return -1;
    ListNode* node = cache[key];
    moveToHead(node);
    return node->value;
}

void put(int key, int value) {
    if (cache.find(key) != cache.end()) {
        ListNode* node = cache[key];
        node->value = value;
        moveToHead(node);
    } else {
        ListNode* newNode = new ListNode(key, value);
        cache[key] = newNode;
        addToHead(newNode);

        if (cache.size() > capacity) {
            ListNode* removed = popTail();
            cache.erase(removed->key);
            delete removed;
        }
    }
}

~LRUCache() {
    for (auto& pair : cache) {
        delete pair.second;
    }
    delete head;
    delete tail;
}

};

int main() {
    LRUCache lru(2);
    lru.put(1, 1);
    lru.put(2, 2);
    cout << lru.get(1) << endl; // 输出 1
    lru.put(3, 3);               // 淘汰 key=2
    cout << lru.get(2) << endl; // 输出 -1
    return 0;
}