力扣Hot100每日N题（17~18）

148. 排序链表

链表归并排序，但是太麻烦了不想学了

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {List<Integer> list = new ArrayList<>();ListNode temp = head;while(temp != null){list.add(temp.val);temp = temp.next;}Collections.sort(list);temp = head;int index = 0;while(temp != null){temp.val = list.get(index);index++;temp = temp.next;}return head;}
}

146. LRU 缓存

使用哈希表和双端队列
c++版本

struct LinkNode{int key, value;LinkNode* pre;LinkNode* next;LinkNode(): key(0), value(0), pre(nullptr), next(nullptr) {}LinkNode(int _key, int _value): key(_key), value(_value), pre(nullptr), next(nullptr) {}
};
class LRUCache {
private:unordered_map<int, LinkNode*> cache;LinkNode* head;LinkNode* tail;int size;int capacity;
public:LRUCache(int _capacity) {size = 0, capacity = _capacity;head = new LinkNode();tail = new LinkNode();head->next = tail;tail->pre = head;}int get(int key) {if(!cache.count(key)) return -1;LinkNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if(!cache.count(key)){LinkNode* node  = new LinkNode(key, value);cache[key] = node;addToHead(node);if(++size > capacity){LinkNode* removed = removeTail();cache.erase(removed->key);delete removed;--size;}}else{LinkNode* node = cache[key];node->value = value;moveToHead(node);}}void moveToHead(LinkNode* node){removeNode(node);addToHead(node);}LinkNode* removeTail(){LinkNode* node = tail->pre;removeNode(node);return node;}void removeNode(LinkNode* node){node->pre->next = node->next;node->next->pre = node->pre;}void addToHead(LinkNode* node){node->next = head->next;node->pre = head;head->next->pre = node;head->next = node;}};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/

Java版本

class LRUCache {class LinkNode{int key, value;LinkNode pre, next;LinkNode(){key = 0;value = 0;pre = null;next = null;}LinkNode(int _key, int _value){key = _key;value = _value;pre = null;next = null;}}Map<Integer, LinkNode> cache = new HashMap<>();int size, capacity;LinkNode head = new LinkNode();LinkNode tail = new LinkNode();public LRUCache(int _capacity) {size = 0;capacity = _capacity;head.next = tail;tail.pre = head;}public int get(int key) {if(!cache.containsKey(key)) return -1;LinkNode node = cache.get(key);moveToHead(node);return node.value;}public void put(int key, int value) {if(!cache.containsKey(key)){LinkNode node = new LinkNode(key, value);cache.put(key, node);addToHead(node);if(++size > capacity){LinkNode tail = removeTail();cache.remove(tail.key);--size;}}else{LinkNode node = cache.get(key);node.value = value;moveToHead(node);}}void moveToHead(LinkNode node){removeNode(node);addToHead(node);}LinkNode removeTail(){LinkNode node = tail.pre;removeNode(node);return node;}void removeNode(LinkNode node){node.next.pre = node.pre;node.pre.next = node.next;}void addToHead(LinkNode node){node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/