做完這題已經沒有任何力氣寫鏈表題了。

思路很簡單，就是調試特別的痛苦。

老是頻頻報錯，唉。

class LRUCache {
public:struct ListNode{int key,val;ListNode* next; ListNode* prev;ListNode() : key(0), val(0), next(nullptr), prev(nullptr) {}ListNode(int key, int value) : key(key), val(value), next(nullptr), prev(nullptr) {}ListNode(int key, int value, ListNode* next=nullptr, ListNode* prev=nullptr) : key(key), val(value), next(next), prev(prev) {}};ListNode* head=new ListNode();ListNode* tail=head;int capacity;map<int,ListNode*> hash;LRUCache(int capacity) {this->capacity=capacity;}int get(int key) {if(hash.find(key)!=hash.end()){if(head->next==hash[key]) return hash[key]->val;hash[key]->prev->next=hash[key]->next;if(hash[key]->next) hash[key]->next->prev=hash[key]->prev;if(hash[key]==tail) tail=hash[key]->prev;hash[key]->next=head->next;if(head->next) head->next->prev=hash[key];hash[key]->prev=head;head->next=hash[key];return hash[key]->val;}else return -1;}void put(int key, int value) {if(hash.find(key)!=hash.end()){hash[key]->val=value;get(key);return;}else if(capacity==0){hash.erase(tail->key);tail=tail->prev;tail->next=nullptr;}else capacity--;ListNode* newhead=new ListNode(key,value,head->next,head);if(tail==head) tail=newhead;if(head->next) head->next->prev=newhead;head->next=newhead;hash[key]=newhead;}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

看了答案，其實有更好的做法，可以優化并且降低代碼的復雜度，感覺我寫代碼還是太畏縮了。

優化方案一：將頭指針和尾指針都設成虛擬指針，一個指向雙向鏈表頭部的前一個位置，一個指向尾部的后一個位置。（我寫的時候為了節省空間復雜度只弄了一個頭虛擬指針，還是太不敢了）

優化方案二：構造更多的函數，這樣就可以直接調用，代碼邏輯會清晰很多。

于是按這個改進思路又寫了一遍，果然簡單多了……

class LRUCache {
public:struct ListNode{int key,val;ListNode* next; ListNode* prev;ListNode() : key(0), val(0), next(nullptr), prev(nullptr) {}ListNode(int key, int value, ListNode* next=nullptr, ListNode* prev=nullptr) : key(key), val(value), next(next), prev(prev) {}};ListNode* head;ListNode* tail;int capacity;unordered_map<int,ListNode*> hash;LRUCache(int capacity) {this->capacity=capacity;head=new ListNode();tail=new ListNode(0,0,nullptr,head);head->next=tail;}int get(int key) {if(hash.find(key)==hash.end()) return -1;erase(hash[key]);insert(hash[key]);return hash[key]->val;}void put(int key, int value) {if(hash.find(key)!=hash.end()){hash[key]->val=value;erase(hash[key]);insert(hash[key]);return ;}if(capacity>0) capacity--;else if(capacity==0){hash.erase(tail->prev->key);erase(tail->prev);}ListNode* newnode=new ListNode(key,value,nullptr,nullptr);insert(newnode);hash[key]=newnode;}void erase(ListNode* node){node->prev->next=node->next;node->next->prev=node->prev;}void insert(ListNode* node){head->next->prev=node;node->next=head->next;node->prev=head;head->next=node;}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/