排序链表这里说要使用O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间复杂度其实很容易想到需要使用排序因为我们既要保证最终的升序顺序又不能超过O ( n 2 ) O(n^2)O(n2)的时间复杂度所以这里借助归并排序我们使用迭代的方法自下而上不使用递归自上而下因为它的空间复杂度不是常数级思想是什么呢我需要先知道链表长度因为只有知道长度才能知道最终归并排序的次数第一次 每次组合结果是相邻两个元素排好序第二次是相邻四个元素排好序第三次是八个怎么把排好序的链表合并呢可以参考我们之前做过的 合并两个有序链表把两个排好序的链表合并成一个新链表我们想想归并排序我们既然有合并操作就需要有拆分动作因为我们拆分之后才好排序对拆分后的子链表排序组合但是排好序之后我们还需要放回原链表组成一个串所以合并之后是需要返回头节点的。因为我们排序是先排前n个前n个排好之后这些元素的最后一个元素要指向后面排好序的子链表的头节点。/** * 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; } * } */classSolution{publicListNodesortList(ListNodehead){if(headnull)returnhead;intlengthgetLength(head);ListNodedummynewListNode(0,head);// 哨兵节点for(intstep1;steplength;step*2){// 归并排序次数ListNodepreListTaildummy;// 前一个已经排好序的尾节点ListNodecurdummy.next;while(cur!null){// 拆分相当于 2-1-3 拆分为了 2, 1, 3ListNodehead1cur;ListNodehead2splitList(head1,step);cursplitList(head2,step);// 下一组需要排序的// 归并2, 1, 3 变为 1-2, 3ListNode[]headTailmerge(head1,head2);// 一次归并排序返回头节点尾节点// 变为 1-2-3preListTail.nextheadTail[0];preListTailheadTail[1];}}returndummy.next;}ListNodesplitList(ListNodehead,intsize){ListNodecurhead;for(inti0;isize-1cur!null;i){curcur.next;}if(curnull||cur.nextnull){returnnull;}ListNodenxtcur.next;cur.nextnull;returnnxt;}intgetLength(ListNodehead){intlength0;while(head!null){length;headhead.next;}returnlength;}ListNode[]merge(ListNodehead1,ListNodehead2){ListNodedummynewListNode();ListNodecurdummy;while(head1!nullhead2!null){if(head1.valhead2.val){cur.nextnewListNode(head1.val);head1head1.next;}else{cur.nextnewListNode(head2.val);head2head2.next;}curcur.next;}cur.nexthead1null?head2:head1;while(cur.next!null){curcur.next;}returnnewListNode[]{dummy.next,cur};}}LRU缓存第一种方式也就是直接利用 Java 的库双向链表LinkedHashMap它非常适合用来实现 LRU它是一个双向链表并且在构造方法中指定accessOrder为 true 的话会在访问元素的时候把元素移动到链表尾部这样链表首元素就是最近最少被访问的元素它还提供一个方法removeEldestEntry它会返回一个返回值告诉LinkedHashMap是否需要移除链表首元素。classLRUCacheextendsLinkedHashMapInteger,Integer{privatefinalintcapacity;publicLRUCache(intcapacity){super(capacity,0.75f,true);// 第二个参数用默认值 0.75f 就行第三个即 accessOrderthis.capacitycapacity;}publicintget(intkey){returnsuper.getOrDefault(key,-1);}OverrideprotectedbooleanremoveEldestEntry(Map.EntryInteger,Integereldest){returnsize()capacity;}}也可以我们自己手写 LRU利用 HashMap 循环链表也就是仿照LinkedHashMap的实现。这里我们链表末尾表示最近最少访问的因为我们对每个节点都有pre有next所以我们只需要一个哨兵节点classLRUCache{// 节点staticclassNode{intkey,val;Nodepre,next;Node(intkey,intval){this.keykey;this.valval;}}privatefinalMapInteger,NodekeyToNodenewHashMap();privatefinalintcapacity;privatefinalNodedummynewNode(0,0);// 哨兵节点publicLRUCache(intcapacity){this.capacitycapacity;dummy.predummy;dummy.nextdummy;// 自己指向自己}publicintget(intkey){if(!keyToNode.containsKey(key)){return-1;}NodexkeyToNode.get(key);remove(x);// 放到链表表头pushFront(x);returnx.val;}privatevoidremove(Nodex){x.pre.nextx.next;x.next.prex.pre;}publicvoidput(intkey,intvalue){// 已经包含则更新值并放入尾部if(keyToNode.containsKey(key)){NodecurkeyToNode.get(key);cur.valvalue;remove(cur);pushFront(cur);}else{// 未包含则放入头部NodenewNodenewNode(key,value);pushFront(newNode);keyToNode.put(key,newNode);if(keyToNode.size()capacity){// 大于容量之后需要移除头节点keyToNode.remove(dummy.pre.key);remove(dummy.pre);}}}privatevoidpushFront(Nodenode){node.nextdummy.next;node.predummy;dummy.next.prenode;dummy.nextnode;}}