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