解题思路：
在O(NlogN)时间复杂度和O(1)常数空间复杂度对链表进行排序。
LRU缓存算法需要查找快、插入快、删除快、有顺序之分。
结合哈希表和双向链表的优点，使用哈希双链表。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92Java:
class LRUCache {
//LRU缓存需要查找快、插入快、删除快、元素间有顺序
//结点定义
class Node{
public int key,val;
public Node next,prev;
public Node(int k,int v){
this.key = k;
this.val = v;
}
}
//双向链表定义
class DoubleList{
private Node head,tail;
private int size;
public DoubleList(){
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.prev = head;
size = 0;
}
public void addFirst(Node x){
x.next = head.next;
x.prev = head;
head.next.prev = x;
head.next = x;
size++;
}
public void remove(Node x){
x.prev.next = x.next;
x.next.prev = x.prev;
size --;
}
public Node removeLast(){
if(tail.prev == head)
return null;
Node last = tail.prev;
remove(last);
return last;
}
public int size(){
return size;
}
}
private HashMap<Integer,Node> map;
private DoubleList cache;
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
//取出值，然后把值放在头部
int val = map.get(key).val;
put(key,val);
return val;
}
public void put(int key, int value) {
Node x = new Node(key,value);
if(map.containsKey(key)){//如果关键字存在,删除原结点，再在头部添加，更新哈希映射
cache.remove(map.get(key));
cache.addFirst(x);
map.put(key,x);
}else{
if(cap == cache.size()){//如果缓存到达上限，腾出最后尾部位置
Node last = cache.removeLast();
map.remove(last.key);//删除最后一个位置的哈希映射
}
cache.addFirst(x);
map.put(key,x);
}
}
}
//https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
