题解 | #反转链表#

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    static class Node {
        int key ;
        int val ;
        Node next ;
        Node pre ;
        Node(int key , int val) {
            this.key = key ;
            this.val = val ;
        }
    }
    //思想就是，使用map来存储数据，使用双向链表来维持 值的使用情况
    Map<Integer,Node> map = new HashMap<>() ;
    Node head = new Node(-1,-1) ;
    Node tail = new Node(-1,-1) ;
    int size ;
    public int[] LRU (int[][] operators, int k) {
        this.size = k ;
        head.next = tail ;
        tail.pre = head ;
        int len = 0 ;
        for(int i = 0 ; i < operators.length ; i ++) {
            if(operators[i].length == 2) {
                len ++ ;
            }
        }
        int[] res = new int[len] ;
        len = 0 ;
        for(int i = 0 ; i < operators.length ; i ++) {
            if(operators[i].length == 2) {
                res[len ++] = get(operators[i][1]) ;
            } else {
                set(operators[i][1],operators[i][2]) ;
            }
        }
        return res ;
    }
    public void set(int key , int value) {
        if(map.get(key) == null) {
            if(map.size() >= size) {
                //移除队尾
                Node n1 = tail.pre ;
                tail.pre.pre.next = tail ;
                tail.pre = tail.pre.pre ;
                map.remove(n1.key) ;
            }
            Node node = new Node(key,value) ;
            moveToHead(node) ;
            map.put(key , node) ;
        } else {//已经存在，覆盖，后提升到头部
            Node node = map.get(key) ;
            node.val = value ;
            node.pre.next = node.next ;
            node.next.pre = node.pre ;
            moveToHead(node) ;
        }
    }
    public int get(int key) {
        if(map.get(key) == null) {
            return -1 ;
        } else {
            Node node = map.get(key) ;
            node.pre.next = node.next ;
            node.next.pre = node.pre ;
            moveToHead(node) ;
            return node.val ;
        }
    }
    public void moveToHead(Node node) {
        node.next = head.next ;
        head.next.pre = node ;
        head.next = node ;
        node.pre = head ;
    }
}