HashTable + Single Linked List (java with explaination in comment)

  • 0
    public class LRUCache {
        class ListNode
            public int data;
            public int key;
            public ListNode next;
            public ListNode(int data,int key) {
                this.data = data;
                this.key = key;
        int size;
        ListNode head;
        ListNode tail;
        HashMap<Integer,ListNode> m;
        public LRUCache(int capacity) {
            head = new ListNode(-1,-1);
            m = new HashMap<>();
            size = capacity;
        public int get(int key) {
            int res = -1;
            if(m.containsKey(key)){//key contains
                ListNode beforeTar = m.get(key);//get the target node's parent
                res = beforeTar.next.data; //set the target node's val to res
                if(n!=head){//check if need to make the target node to first one
                    if(n.next==tail)//check if target node is tail
                        tail = n;//set tail to target node's parent
                    ListNode tmp = head.next;//save origin first node
                    m.put(tmp.key,n.next);//update previous first node parent to target node
                    m.put(key,head);//update target node parent to head
                    if(n.next.next!=null)//if target node's next is not null, update target node's next's parent to target node's parent
                    head.next = n.next;//set target node as first node
                    n.next = n.next.next;//set target node's parent'next to target node's next .
                    head.next.next = tmp;//set cur first node's next to previous first node
            return res;
        public void put(int key, int value) {
                m.get(key).next.data = value;//update value
                get(key);//use get to make it goto first node
                if(m.size()==size){//remove tail in hashmap and update tail node
                    ListNode tailParent = m.get(tail.key);
                    tailParent.next = null;
                    tail = tailParent; 
                ListNode tmp = head.next;//cur first node saved in tmp
                head.next = new ListNode(value,key);//creat new node,let head.next point to it
                if(m.size()==0) tail = head.next;//if no element, initialize tail
                head.next.next = tmp;//new node.next point to previous first node
                m.put(key,head);//add new node key, and its parent is head
                if(tmp!=null)//if previous first node is not null, update its parent from head to new node

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.