双向链表

与单链表相比，双向链表多了一个指向其前一个节点的指针，在实际使用时，通常使用两个哑节点分别作为哑头节点和哑尾节点，方便操作。

// 节点类
class DLinkedNode{
    int val;
    DLinkedNode prev;
    DLinkedNode next;
    public DLinkedNode(){}
    public DLinkedNode(int _val) {val = _val;}
}

题目：

146. LRU 缓存机制

思路：

哈希表可以在$O(1)$时间内返回在双向链表中的节点，而双向链表又可以在$O(1)$时间内完成以下几个操作：

1：删除一个节点

2：将一个节点移动到链表的头部或者尾部

所以当每次有操作时，将被操作的节点移动到链表头，保证靠近链表头的节点都是最近使用过的。然后如果链表长度超过缓存容量时，删除尾部节点。

从而在$O(1)$时间内，实现了LRU（最近最少使用）的各种操作。

class LRUCache {
    private int capacity;
    private int size;
    private HashMap<Integer, DLinkedNode> cache;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new HashMap<>();
        // 哑头节点和尾节点
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if(node == null){
            // 操作系统中发生缺页中断，此后会将该页调入缓存
            return -1;
        }
        // 将该node移动到链表头部
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // key 不存在，新建node
            DLinkedNode newNode = new DLinkedNode(key, value);
            addToHead(newNode);
            cache.put(key, newNode);
            size++;
            // 容量超出限制
            if (size > capacity) {
                // 删除尾部的节点
                DLinkedNode tailNode = removeTail();
                cache.remove(tailNode.key);
                size--;
            }
        } else {
            // key 已经存在，跟新其值，并将node移动到链表头
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    // 从链表中中删除指定节点
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private DLinkedNode removeTail() {
        DLinkedNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;        
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
}

class DLinkedNode{
    int key;
    int value;
    DLinkedNode next;
    DLinkedNode prev;
    // 空构造函数
    public DLinkedNode() {}
    public DLinkedNode(int _key, int _value) {
        key = _key;
        value = _value;
    }
}

LFU缓存：最不经常使用缓存

460. LFU 缓存

关键点：需要替换节点时，需要删除使用次数最少（次数相同时删除最久未被使用）的节点

class LFUCache {
    // 映射键值到节点
    HashMap<Integer, Node> keyToNode = new HashMap<>();
    // 映射使用次数到对应的所有节点
    HashMap<Integer, LinkedList<Node>> frequentToNodes = new HashMap<>();
    // cache容量、当前最小出现频率(也可以用TreeMap来存储频率哈希表，但是这样插入和查找最小频率时间为：log n)
    int capacity, minFrequent = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFrequent = 1;
    }
    
    public int get(int key) {
        if (this.capacity == 0) return -1;
        if (!keyToNode.containsKey(key)) return -1;
        Node node = keyToNode.get(key);
        LinkedList<Node> now = frequentToNodes.get(node.cnt);
        now.remove(node);
        if (now.isEmpty()) {
            // 更新最小频率
            if (this.minFrequent == node.cnt) minFrequent++;
            frequentToNodes.remove(node.cnt);
        } else frequentToNodes.put(node.cnt, now);
        node.cnt++;
        frequentToNodes.computeIfAbsent(node.cnt, k -> new LinkedList<>()).offerLast(node);
        return node.val;
    }
    
    public void put(int key, int val) {
        if (this.capacity == 0) return;
        // key已经存在，更新其值
        if (keyToNode.containsKey(key)) {
            Node node = keyToNode.get(key);
            LinkedList<Node> now = frequentToNodes.get(node.cnt);
            now.remove(node);
            if (now.isEmpty()) {
                // 更新最小频率
                if (this.minFrequent == node.cnt) minFrequent++;
                frequentToNodes.remove(node.cnt);
            } else frequentToNodes.put(node.cnt, now);
            node.cnt++;
            node.val = val;
            frequentToNodes.computeIfAbsent(node.cnt, k -> new LinkedList<>()).offerLast(node);
        } else {
            // cache还有剩余容量，直接加入
            if (this.keyToNode.size() < this.capacity) {
                Node node = new Node(key, val, 1);
                frequentToNodes.computeIfAbsent(1, k -> new LinkedList<>()).offerLast(node);
                keyToNode.put(key, node);
            } else {
                // 没有剩余容量，需要删除使用次数最少（次数相同时删除最久未被使用）的节点
                LinkedList<Node> now = frequentToNodes.get(minFrequent);
                keyToNode.remove(now.pollFirst().key);
                if (now.isEmpty()) frequentToNodes.remove(minFrequent);
                else frequentToNodes.put(minFrequent, now);
                Node node = new Node(key, val, 1);
                frequentToNodes.computeIfAbsent(1, k -> new LinkedList<>()).offerLast(node);
                keyToNode.put(key, node);
            }
            // 新加入一个节点，最少出现频率置为1
            minFrequent = 1;
        }
    }
}

class Node {
    int val, cnt, key;

    public Node(int key, int val, int cnt) {
        this.val = val;
        this.key = key;
        this.cnt = cnt;
    }
}

环形链表

链表判断是否有环

• 快慢指针法（Floyd判圈）：还可以求环的长度、环的起点

public boolean hasCycle(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && slow != null) {
        slow = slow.next;
        fast = fast.next;
        if (fast != null) fast = fast.next;
        else return false;
        if (fast == slow) {
            // 求环的长度
            int cnt = 1;
            while (fast.next != slow) {
                cnt++;
                fast = fast.next;
            }
            // System.out.println(cnt);
            // 求环的起点
            fast = head;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            // System.out.println(fast.val);
            return true;
        } 
    }
    return false;
}