每日两题 / 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);
 */