【链表】【中等】两数相加/倒N删除/两个交换/排序链表/LRU缓存

两数相加逐位相加原题链接两个链表逐位走当前位 % 10进位 / 10剩余 carry 标记进位publicstaticListNodeaddTwoNumbers(ListNodel1,ListNodel2){ListNoderesnewListNode(0);ListNodecurres;intcarry0;//进位标识//l1和l2全为null时跳出循环while(l1!null||l2!null){intx(l1!null)?l1.val:0;inty(l2!null)?l2.val:0;intsumxycarry;carrysum/10;intvalsum%10;cur.nextnewListNode(val);curcur.next;if(l1!null)l1l1.next;if(l2!null)l2l2.next;}if(carry1){cur.nextnewListNode(1);}returnres.next;}删除链表的倒数第N个节点快慢指针 固定间距原题链接注意考虑删除节点为第一个节点的情况-虚拟头节点publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummynewListNode(-1);dummy.nexthead;ListNodefastdummy;ListNodeslowdummy;for(inti0;in;i){fastfast.next;}while(fast!null){fastfast.next;slowslow.next;}slow.nextslow.next.next;returndummy.next;}两两交换链表中的节点两两一组判别原题链接注意先后顺序right.next 的改变应该在 left right.next 之前publicstaticListNodeswapPairs(ListNodehead){ListNodedummynewListNode(0);dummy.nexthead;ListNodeprevdummy;while(prev.next!nullprev.next.next!null){ListNodeleftprev.next;ListNoderightprev.next.next;prev.nextright;left.nextright.next;right.nextleft;prevleft;}returndummy.next;}排序链表归并排序原题链接使用插入排序会进行两层循环结果超时① 找中点↓② 切成两个链表↓③ 左右分别递归排序↓④ merge 两个有序链表publicstaticListNodesortList(ListNodehead){if(headnull||head.nextnull){returnhead;}//先使用快慢指针将链表分为两半ListNodeslowhead;ListNodefasthead;while(fast.next!nullfast.next.next!null){slowslow.next;fastfast.next.next;}ListNodep1head;ListNodep2slow.next;slow.nextnull;p1sortList(p1);p2sortList(p2);//合并两个有序链表returnmergeTwoLists(p1,p2);}//mergeTwoLists方法publicstaticListNodemergeTwoLists(ListNodel1,ListNodel2){ListNodedummynewListNode(0);ListNodeheaddummy;while(l1!nulll2!null){if(l1.vall2.val){head.nextl1;l1l1.next;}else{head.nextl2;l2l2.next;}headhead.next;}head.nextl1!null?l1:l2;returndummy.next;}LRU缓存原题链接addToHead这个节点现在不在链表里把它插到头部moveToHead这个节点已经在链表里先删掉再重新插到头部注意进行区分否则新节点会空指针异常publicclassLRUCache{privateclassDListNode{intkey;intval;DListNodeprev;DListNodenext;publicDListNode(intkey,intval){this.keykey;this.valval;}}intcapacity;//缓存容量intsize;//当前已经存在的节点数量MapInteger,DListNodemapnewHashMap();DListNodedummy_head;DListNodedummy_tail;publicLRUCache(intcapacity){this.capacitycapacity;size0;dummy_headnewDListNode(-1,-1);dummy_tailnewDListNode(-1,-1);dummy_head.nextdummy_tail;dummy_tail.prevdummy_head;}publicintget(intkey){if(!map.containsKey(key)){return-1;}DListNodenodemap.get(key);moveToHead(node);returnnode.val;}publicvoidput(intkey,intvalue){//如果key存在直接更新值if(map.containsKey(key)){DListNodenodemap.get(key);node.valvalue;moveToHead(node);return;}if(sizecapacity){//如果缓存已满删除尾部节点DListNodetaildummy_tail.prev;map.remove(tail.key);removeNode(tail);size--;}//添加新节点到头部DListNodenodenewDListNode(key,value);map.put(key,node);addToHead(node);size;}privatevoidremoveNode(DListNodenode){node.prev.nextnode.next;node.next.prevnode.prev;}//将节点添加到头部(节点原来不存在)privatevoidaddToHead(DListNodenode){node.prevdummy_head;node.nextdummy_head.next;dummy_head.next.prevnode;dummy_head.nextnode;}//将节点移动到头部(节点原来存在)privatevoidmoveToHead(DListNodenode){removeNode(node);addToHead(node);}}