编辑代码

//双向链表+hash


function ListNode(key,val) {
	this.key = key
	this.val = val
	this.next =null
	this.prev =null
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
	this.hash = {}
	this.capacity = capacity
	this.head = new ListNode()
	this.tail = new ListNode()
	this.head.next = this.tail
	this.tail.prev = this.head
	this.length = 0
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
	let n = this.hash[key]
	if(n!=undefined){
		this.moveToHead(n)
		return n.val
	}
	return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
	let node = new ListNode(key, value)
	let n = this.hash[key]
	if(n){
		this.removeNode(n)
		this.addToHead(node)
	}else{
		if (this.length >= this.capacity) {
			delete this.hash[this.tail.prev.key]
			this.removeNode(this.tail.prev)
		} else {
			this.length++
		}
		// 更新head
		this.addToHead(node)
	}
	//保存hash
	this.hash[key] = node
};


LRUCache.prototype.moveToHead = function(node){
	this.removeNode(node)
	this.addToHead(node)
}

LRUCache.prototype.removeNode = function (node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}
LRUCache.prototype.addToHead = function (node) {
	node.next = this.head.next
	node.next.prev = node
	node.prev = this.head
	this.head.next = node
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */