兩數(shù)相加逐位相加原題鏈接兩個(gè)鏈表逐位走當(dāng)前位 % 10進(jìn)位 / 10剩余 carry 標(biāo)記進(jìn)位publicstaticListNodeaddTwoNumbers(ListNodel1,ListNodel2){ListNoderesnewListNode(0);ListNodecurres;intcarry0;//進(jìn)位標(biāo)識(shí)//l1和l2全為null時(shí)跳出循環(huán)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;}刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)快慢指針 固定間距原題鏈接注意考慮刪除節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)的情況-虛擬頭節(jié)點(diǎ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;}兩兩交換鏈表中的節(jié)點(diǎn)兩兩一組判別原題鏈接注意先后順序right.next 的改變應(yīng)該在 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;}排序鏈表歸并排序原題鏈接使用插入排序會(huì)進(jìn)行兩層循環(huán)結(jié)果超時(shí)① 找中點(diǎn)↓② 切成兩個(gè)鏈表↓③ 左右分別遞歸排序↓④ merge 兩個(gè)有序鏈表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);//合并兩個(gè)有序鏈表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這個(gè)節(jié)點(diǎn)現(xiàn)在不在鏈表里把它插到頭部moveToHead這個(gè)節(jié)點(diǎn)已經(jīng)在鏈表里先刪掉再重新插到頭部注意進(jìn)行區(qū)分否則新節(jié)點(diǎn)會(huì)空指針異常publicclassLRUCache{privateclassDListNode{intkey;intval;DListNodeprev;DListNodenext;publicDListNode(intkey,intval){this.keykey;this.valval;}}intcapacity;//緩存容量intsize;//當(dāng)前已經(jīng)存在的節(jié)點(diǎn)數(shù)量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){//如果緩存已滿刪除尾部節(jié)點(diǎn)DListNodetaildummy_tail.prev;map.remove(tail.key);removeNode(tail);size--;}//添加新節(jié)點(diǎn)到頭部DListNodenodenewDListNode(key,value);map.put(key,node);addToHead(node);size;}privatevoidremoveNode(DListNodenode){node.prev.nextnode.next;node.next.prevnode.prev;}//將節(jié)點(diǎn)添加到頭部(節(jié)點(diǎn)原來(lái)不存在)privatevoidaddToHead(DListNodenode){node.prevdummy_head;node.nextdummy_head.next;dummy_head.next.prevnode;dummy_head.nextnode;}//將節(jié)點(diǎn)移動(dòng)到頭部(節(jié)點(diǎn)原來(lái)存在)privatevoidmoveToHead(DListNodenode){removeNode(node);addToHead(node);}}