|149|[Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_149.java)| O(?)|O(?)| Hard|

|148|[Sort List](https://leetcode.com/problems/sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_148.java) O(nlogn)|O(h) | Medium| Linked List, Sort

|147|[Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_147.java) O(n^2)|O(1) | Medium| Linked List

|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Solution](../master/leetcode-algorithms/src/main/java/com/fishercoder/solutions/_146.java)| amortized O(1)| O(n) | Hard| Linked List

|146|[LRU Cache](https://leetcode.com/problems/lru-cache/)|[Solution](../master/leetcode-algorithms/src/main/java/com/fishercoder/solutions/_146.java)| amortized O(1)| O(k) | Hard|DoublyLinked List, LinkedHashMap

|145|[Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_145.java)| O(n)|O(h) | Hard| Binary Tree

|144|[Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_144.java)| O(n)|O(h) | Medium| Binary Tree

|143|[Reorder List](https://leetcode.com/problems/reorder-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_143.java)| O(n)|O(1)| Medium|

publicclass_146 {

publicclassLinkedHashMapSolution {

publicclassSolution1 {

privateMap<Integer,Integer>cache;

privatefinalintmax;

publicLinkedHashMapSolution(intcapacity) {

publicSolution1(intcapacity) {

max =capacity;

cache =newLinkedHashMap<Integer,Integer>(capacity,1.0f,true) {

publicbooleanremoveEldestEntry(Map.Entryeldest) {

}

}

publicclassDoublyLinkedListPlusHashMapSolution {

publicclassSolution2 {

privateclassNode {

intkey;

intvalue;

DoublyLinkedListPlusHashMapSolution.Nodeprev;

DoublyLinkedListPlusHashMapSolution.Nodenext;

Solution2.Nodeprev;

Solution2.Nodenext;

Node(intk,intv) {

this.key =k;

privateintcapacity;

privateintcount;

privateDoublyLinkedListPlusHashMapSolution.Nodehead;

privateDoublyLinkedListPlusHashMapSolution.Nodetail;

privateMap<Integer,DoublyLinkedListPlusHashMapSolution.Node>map;

privateSolution2.Nodehead;

privateSolution2.Nodetail;

privateMap<Integer,Solution2.Node>map;

publicDoublyLinkedListPlusHashMapSolution(intcapacity) {

publicSolution2(intcapacity) {

this.capacity =capacity;

this.count =0;// we need a count to keep track of the number of elements in the cache so

this.map =newHashMap();

head =newDoublyLinkedListPlusHashMapSolution.Node();

tail =newDoublyLinkedListPlusHashMapSolution.Node();

head =newSolution2.Node();

tail =newSolution2.Node();

head.next =tail;

tail.prev =head;

}

publicintget(intkey) {

DoublyLinkedListPlusHashMapSolution.Nodenode =map.get(key);

Solution2.Nodenode =map.get(key);

if (node ==null) {

return -1;

}

publicvoidset(intkey,intvalue) {

DoublyLinkedListPlusHashMapSolution.Nodenode =map.get(key);

Solution2.Nodenode =map.get(key);

if (node ==null) {

node =newDoublyLinkedListPlusHashMapSolution.Node(key,value);

node =newSolution2.Node(key,value);

map.put(key,node);

add(node);

count++;

DoublyLinkedListPlusHashMapSolution.NodetoDelete =tail.prev;

Solution2.NodetoDelete =tail.prev;

map.remove(toDelete.key);

remove(toDelete);

count--;

}

}

privatevoidremove(DoublyLinkedListPlusHashMapSolution.Nodenode) {

DoublyLinkedListPlusHashMapSolution.Nodenext =node.next;

DoublyLinkedListPlusHashMapSolution.Nodeprev =node.prev;

privatevoidremove(Solution2.Nodenode) {

Solution2.Nodenext =node.next;

Solution2.Nodeprev =node.prev;

prev.next =next;

next.prev =prev;

}

privatevoidadd(DoublyLinkedListPlusHashMapSolution.Nodenode) {

privatevoidadd(Solution2.Nodenode) {

DoublyLinkedListPlusHashMapSolution.Nodenext =head.next;

Solution2.Nodenext =head.next;

head.next =node;

node.next =next;

node.prev =head;