每日两题 / 142. 环形链表 II 146. LRU 缓存（LeetCode热题100）

本文主要是介绍每日两题 / 142. 环形链表 II 146. LRU 缓存（LeetCode热题100），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

142. 环形链表 II - 力扣（LeetCode）

用哈希记录走过的节点即可

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *cur = head;set<ListNode*> s;while (cur) {if (s.count(cur)) {return cur;}s.insert(cur);cur = cur->next;}return nullptr;}
};

146. LRU 缓存 - 力扣（LeetCode）
$O (1)$ 地查找并修改kv结构，用unordered_map即可解决
问题是题目要求：哈希表容量有限，超出容量时，将删除最久未访问的kv
那么关键就在于：如何用数据结构表示访问的先后顺序？显然哈希表无法做到
越靠近链表的头指针，越经常访问该元素。为何不用数组？越靠近首元素/尾元素，越经常访问该元素？维护访问顺序时，对于数组，需要 $O (n)$ 地移动数组中的元素
对于链表，只需要 $O (1)$ 地修改节点，显然链表在时间上更优且满足题意

对于最近访问的元素，若不在链表中，则创建新节点并插入链表头（添加），若在链表中，则将其移动到链表头（删除+增加）。综上，我们的链表需要（增加+删除）这两个操作，显然使用双向链表更优
最后的问题是：在链表中如何 $O (1)$ 地查找某个元素？显然链表无法作用，所以使用哈希表作为辅助结构，存储key值与其在链表中的位置（节点地址）

struct Node {int val, key;Node *prev = nullptr;Node *next = nullptr;
};class LRUCache {public:Node *head;Node *tail;unordered_map<int, Node*> mp;int capacity;void addToHead(Node *node) {Node *first = head->next;head->next = node, first->prev = node;node->next = first, node->prev = head;}void delNode(Node *node) {Node *prev = node->prev;Node *next = node->next;prev->next = next;next->prev = prev;}LRUCache(int capacity) {head = new Node;tail = new Node;head->next = tail, head->prev = tail;tail->next = head, tail->prev = head;this->capacity = capacity;}int get(int key) {if (mp.count(key)) {delNode(mp[key]);addToHead(mp[key]);return mp[key]->val;}return -1;}void put(int key, int value) {if (mp.count(key)) {mp[key]->val = value;delNode(mp[key]);addToHead(mp[key]);}else {mp[key] = new Node;mp[key]->val = value, mp[key]->key = key;addToHead(mp[key]);}if (mp.size() > capacity) {Node *Del = tail->prev;mp.erase(Del->key);delNode(Del);delete Del;}}
};/*** 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);*/