1. 為什么這道題值得反復(fù)刷三遍1.1 題目本身到底在考什么兩數(shù)相加在力扣上是第2題屬于那種看起來特別簡(jiǎn)單、寫起來全是細(xì)節(jié)的經(jīng)典題目。題面講得很直白給你兩個(gè)非空的鏈表每個(gè)節(jié)點(diǎn)存一位數(shù)字?jǐn)?shù)字是逆序存儲(chǔ)的也就是鏈表頭節(jié)點(diǎn)對(duì)應(yīng)的是個(gè)位要求把兩個(gè)數(shù)相加返回一個(gè)新的鏈表同樣用逆序存儲(chǔ)。我第一次刷這道題的時(shí)候心想這不就是豎式加法嘛個(gè)位對(duì)齊、逢十進(jìn)一小學(xué)生都會(huì)。結(jié)果真上手寫代碼的時(shí)候第一版直接崩了原因是我用了那種先把鏈表轉(zhuǎn)成數(shù)字加完再轉(zhuǎn)回鏈表的偷懶寫法——兩個(gè)鏈表各循環(huán)一遍拼成整數(shù)相加然后再循環(huán)取每一位構(gòu)建新鏈表。用例一多直接撞上整型溢出。那一刻我才意識(shí)到這道題考的根本不是你會(huì)不會(huì)加法而是你懂不懂鏈表這種數(shù)據(jù)結(jié)構(gòu)的操作細(xì)節(jié)能不能在指針移動(dòng)、節(jié)點(diǎn)創(chuàng)建、邊界判斷這些瑣碎環(huán)節(jié)里不犯錯(cuò)。力扣把這道題放在鏈表專題的前幾道位置很講究。它既不像兩數(shù)之和那樣依賴哈希表的巧妙映射也不像反轉(zhuǎn)鏈表那樣只有一個(gè)核心動(dòng)作。兩數(shù)相加恰好卡在中間算法思路簡(jiǎn)單到透明工程實(shí)現(xiàn)卻暗藏七八個(gè)容易翻車的點(diǎn)。對(duì)刷題新手來說這是一道完美的從看題解到自己寫的過渡題對(duì)準(zhǔn)備面試的人來說這也是面試官最愛拿來試探候選人代碼基本功的題目之一因?yàn)橐粋€(gè)小時(shí)內(nèi)從思路溝通、邊界確認(rèn)到寫碼調(diào)試全部流程都能暴露出來。這道題真正在考察的能力清單在我看來是這幾項(xiàng)第一能不能識(shí)別出逆序存儲(chǔ)這個(gè)條件其實(shí)是在故意降低難度——個(gè)位對(duì)齊意味著兩個(gè)鏈表的頭節(jié)點(diǎn)就是低位不用做任何反轉(zhuǎn)預(yù)處理第二能不能意識(shí)到直接用整數(shù)運(yùn)算會(huì)溢出從而第一時(shí)間拋棄轉(zhuǎn)數(shù)字再相加的路徑第三能不能在鏈表的循環(huán)中同時(shí)處理兩個(gè)不同長(zhǎng)度的鏈表、進(jìn)位標(biāo)記、以及結(jié)果鏈表尾部可能多出來的節(jié)點(diǎn)。這三個(gè)能力點(diǎn)恰好對(duì)應(yīng)了鏈表操作的三大基本功遍歷、構(gòu)造、邊界處理。1.2 最容易踩的數(shù)值溢出直覺坑先把這個(gè)最經(jīng)典的坑單獨(dú)拎出來說因?yàn)樗菂^(qū)分背過題解和真理解的分水嶺。很多人第一次看到這道題的直覺反應(yīng)是把兩個(gè)鏈表里的數(shù)字取出來轉(zhuǎn)成 int 或者 long加起來再轉(zhuǎn)回鏈表。這個(gè)思路在小學(xué)數(shù)學(xué)層面完全正確在工程層面卻是個(gè)定時(shí)炸彈。力扣的題目約束里明確寫過鏈表長(zhǎng)度范圍雖然不同版本的題面措辭會(huì)有調(diào)整但實(shí)戰(zhàn)中你大概率會(huì)遇到超長(zhǎng)鏈表。Java 的 int 最大約21億long 最大約922億億聽起來很大可一旦鏈表長(zhǎng)度超過10位long 就開始吃力超過19位long 直接溢出。力扣的測(cè)試用例里出現(xiàn)幾十位甚至上百位的數(shù)字是常態(tài)你辛辛苦苦把鏈表轉(zhuǎn)成數(shù)值結(jié)果相加的一瞬間數(shù)據(jù)就錯(cuò)了然后你還得花大量時(shí)間排查我明明加了為什么結(jié)果不對(duì)。更隱蔽的問題是即使語言支持高精度數(shù)值比如 Python 的 int 無上限這種做法也繞了一個(gè)大彎為了算加法你先把鏈表結(jié)構(gòu)拆散成數(shù)值算完又要用取模和整除把它重新組裝成鏈表時(shí)空效率都很虧。而且這種寫法完全丟失了這道題想考察的鏈表操作能力面試官看到這種解法基本會(huì)直接判定基礎(chǔ)不扎實(shí)。正確的思路是模擬豎式加法的手算過程兩個(gè)指針分別從兩個(gè)鏈表頭出發(fā)每一位上的數(shù)字相加再加上上一位的進(jìn)位結(jié)果對(duì)10取模得到當(dāng)前位對(duì)10整除得到進(jìn)位然后兩個(gè)指針同時(shí)后移。這個(gè)過程不需要把任何數(shù)據(jù)轉(zhuǎn)成數(shù)值天然避開了溢出問題也天然適配了鏈表的結(jié)構(gòu)。想通這一點(diǎn)這道題的算法骨架就已經(jīng)在腦子里了。2. 逆序鏈表的結(jié)構(gòu)拆解與指針細(xì)節(jié)2.1 鏈表節(jié)點(diǎn)定義與輸入數(shù)據(jù)的真實(shí)含義力扣的鏈表節(jié)點(diǎn)定義是經(jīng)典的單鏈表結(jié)構(gòu)在代碼里通常是這樣一個(gè)類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; } }Python 版本對(duì)應(yīng)的是class ListNode: def __init__(self, val0, nextNone): self.val val self.next next理解逆序存儲(chǔ)這四個(gè)字是讀懂這道題的前提。以數(shù)字 342 為例它對(duì)應(yīng)的鏈表是 2 - 4 - 3也就是頭節(jié)點(diǎn)是 2第二個(gè)節(jié)點(diǎn)是 4尾節(jié)點(diǎn)是 3。為什么力扣要設(shè)計(jì)成逆序從數(shù)據(jù)結(jié)構(gòu)的角度看這個(gè)設(shè)計(jì)非常聰明兩個(gè)數(shù)字相加是從低位開始的而鏈表的遍歷只能從頭部開始逆序存儲(chǔ)剛好讓最低位和鏈表的遍歷起點(diǎn)重合這樣一來你不需要做任何反轉(zhuǎn)操作直接從頭開始逐位相加就是正確的計(jì)算順序。這種存儲(chǔ)順序和計(jì)算順序一致的設(shè)計(jì)在工程里其實(shí)很常見?；叵胍幌挛覀兪謱懾Q式加法時(shí)習(xí)慣上把個(gè)位寫在最右邊從右往左算但計(jì)算機(jī)遍歷鏈表只能從左往右走所以把個(gè)位放在鏈表頭就成了為了遍歷方便而調(diào)整存儲(chǔ)順序的典型例子。類似的思路在很多大數(shù)運(yùn)算庫中也有體現(xiàn)比如某些高精度計(jì)算庫會(huì)把數(shù)字按低位在前的方式存儲(chǔ)在數(shù)組中目的就是讓運(yùn)算循環(huán)從下標(biāo)0開始省去反轉(zhuǎn)操作。實(shí)際的輸入數(shù)據(jù)長(zhǎng)什么樣題目保證兩個(gè)鏈表都是非空的每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)字范圍是 0 到 9。這里有個(gè)容易忽略的細(xì)節(jié)雖然每個(gè)節(jié)點(diǎn)是一位數(shù)但兩個(gè)鏈表的長(zhǎng)度可以完全不同。比如第一個(gè)鏈表代表 1 - 3 - 5 - 7數(shù)字 7531第二個(gè)鏈表代表 9 - 2數(shù)字 29兩個(gè)鏈表長(zhǎng)度分別是4和2。這意味著你的循環(huán)條件不能只盯著其中一個(gè)鏈表必須同時(shí)考慮兩個(gè)鏈表都還有節(jié)點(diǎn)或者進(jìn)位還不為0這三種情況。還有一個(gè)隱含信息是兩個(gè)數(shù)本身不會(huì)以 0 開頭除非這個(gè)數(shù)本身就是 0。所以你不會(huì)遇到鏈表里存了一大串前導(dǎo)零這種無意義的情況這也簡(jiǎn)化了邊界處理。但非空不等于不會(huì)出現(xiàn) 0比如一個(gè)鏈表只有一個(gè)節(jié)點(diǎn) val0這種情況是完全合法的你的代碼必須能正確處理 0 加上任意數(shù)。2.2 虛擬頭節(jié)點(diǎn)一個(gè)讓代碼簡(jiǎn)潔一半的慣用法寫鏈表算法題的時(shí)候虛擬頭節(jié)點(diǎn)dummy head可以說是我最依賴的技巧之一兩數(shù)相加這道題就是個(gè)很好的示例。如果不使用虛擬頭節(jié)點(diǎn)你需要在循環(huán)開始前單獨(dú)處理結(jié)果鏈表的第一個(gè)節(jié)點(diǎn)先手動(dòng)計(jì)算個(gè)位相加的結(jié)果創(chuàng)建頭節(jié)點(diǎn)然后才開始循環(huán)處理后續(xù)節(jié)點(diǎn)。這個(gè)特判邏輯會(huì)打亂代碼的節(jié)奏而且增加出錯(cuò)概率。使用虛擬頭節(jié)點(diǎn)之后你只需要?jiǎng)?chuàng)建一個(gè)值為任意占位數(shù)的節(jié)點(diǎn)作為起點(diǎn)然后循環(huán)里統(tǒng)一創(chuàng)建新節(jié)點(diǎn)并接在尾節(jié)點(diǎn)后面循環(huán)結(jié)束時(shí)直接返回dummy.next頭節(jié)點(diǎn)的處理被完全抹平了。dummy ListNode(0) # 虛擬頭節(jié)點(diǎn)最終返回 dummy.next cur dummy # cur 指向當(dāng)前結(jié)果鏈表的尾節(jié)點(diǎn)這段代碼一寫出來思路立刻就清晰了cur 永遠(yuǎn)指向結(jié)果鏈表的最后一個(gè)節(jié)點(diǎn)每次循環(huán)算出一位結(jié)果就新建一個(gè)節(jié)點(diǎn)掛在 cur 后面然后 cur 后移。整個(gè)過程不需要關(guān)心這是第幾位是不是第一位邏輯完全統(tǒng)一。這里有個(gè)經(jīng)驗(yàn)之談在鏈表的原地操作場(chǎng)景里比如反轉(zhuǎn)鏈表、刪除節(jié)點(diǎn)虛擬頭節(jié)點(diǎn)能省掉大量如果刪除的是頭節(jié)點(diǎn)該怎么辦之類的邊界討論。在兩數(shù)相加這種從零構(gòu)建新鏈表的場(chǎng)景里虛擬頭節(jié)點(diǎn)的作用是統(tǒng)一的節(jié)點(diǎn)創(chuàng)建邏輯避免把答案開頭和其他位置區(qū)別對(duì)待。兩種場(chǎng)景我都建議大家專門練一練因?yàn)樘摂M頭節(jié)點(diǎn)的使用習(xí)慣一旦養(yǎng)成幾乎所有的鏈表構(gòu)造類題目你都能直接套這個(gè)模板。3. 完整解法實(shí)現(xiàn)從偽代碼到可運(yùn)行代碼3.1 核心循環(huán)的每一步在做什么從算法思路上說這道題只需要一個(gè) while 循環(huán)循環(huán)里做四件事取當(dāng)前位的值、求和、計(jì)算當(dāng)前位和進(jìn)位、移動(dòng)指針。我用 Python 寫一版最標(biāo)準(zhǔn)的解法配合注釋看每一步的意圖class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy carry 0 # 進(jìn)位只能是 0 或 1 while l1 or l2 or carry: # 1. 取值鏈表為空時(shí)該位視為 0 v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 # 2. 求和兩個(gè)數(shù)字相加再加上上一位的進(jìn)位 total v1 v2 carry # 3. 計(jì)算當(dāng)前位和進(jìn)位 carry total // 10 cur.next ListNode(total % 10) # 4. 指針全部向后移動(dòng) cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next這段代碼有幾個(gè)值得仔細(xì)品味的點(diǎn)。第一是循環(huán)條件while l1 or l2 or carry這個(gè)條件把三種情況全部包含了兩個(gè)鏈表都沒走完、只有一個(gè)鏈表沒走完、以及兩個(gè)鏈表都走完了但進(jìn)位還沒處理完。初學(xué)者最容易漏的就是第三個(gè)情況比如5 5 10兩個(gè)鏈表都只有一個(gè)節(jié)點(diǎn)相加后得到0但進(jìn)位1需要額外創(chuàng)建一個(gè)節(jié)點(diǎn)掛上去如果循環(huán)條件里不寫or carry這個(gè)進(jìn)位就丟了。第二是取值時(shí)的v1 l1.val if l1 else 0寫法。兩個(gè)鏈表長(zhǎng)度不一樣是常態(tài)短的走完了之后它的每一位都應(yīng)當(dāng)視為0這樣才能繼續(xù)和長(zhǎng)鏈表剩余部分做加法。這種長(zhǎng)度不足就補(bǔ)零的處理方式比先判斷誰長(zhǎng)誰短、然后把短的數(shù)補(bǔ)到和長(zhǎng)的對(duì)齊要優(yōu)雅得多因?yàn)楹笳咝枰~外做鏈表長(zhǎng)度的統(tǒng)計(jì)和節(jié)點(diǎn)的復(fù)制代碼復(fù)雜度直接翻倍。第三是進(jìn)位carry的取值范圍。每一位上三個(gè)數(shù)字相加兩個(gè)數(shù)位加一個(gè)進(jìn)位最大也不會(huì)超過 9 9 1 19所以進(jìn)位只可能是 0 或者 1。不需要考慮進(jìn)位大于1的情況更不需要用數(shù)組來存儲(chǔ)進(jìn)位。這個(gè)結(jié)論看起來簡(jiǎn)單但推導(dǎo)一遍能幫你確認(rèn)算法邏輯的完備性。3.2 循環(huán)結(jié)束后的處理最高位進(jìn)位很多人寫這道題循環(huán)內(nèi)部的邏輯寫得飛快結(jié)果在循環(huán)結(jié)束后的收尾上翻車。前面提到過while條件里包含了or carry這意味著循環(huán)本身已經(jīng)處理了最后一位產(chǎn)生進(jìn)位的情況——當(dāng)兩個(gè)鏈表都遍歷完畢carry 為1時(shí)循環(huán)體會(huì)再執(zhí)行一次此時(shí)兩個(gè)取值都是0total 等于0加0加1等于1創(chuàng)建值為1的新節(jié)點(diǎn)然后進(jìn)位變成0循環(huán)條件才徹底不滿足。為了驗(yàn)證這個(gè)邏輯我們可以手動(dòng)走一遍999 1的例子。鏈表分別是 9 - 9 - 9 和 1計(jì)算過程如下循環(huán)次數(shù)l1當(dāng)前值l2當(dāng)前值carry(進(jìn)前)total當(dāng)前位結(jié)果carry(進(jìn)后)19101001290(鏈表已空)11001390(鏈表已空)1100140(鏈表已空)0(鏈表已空)1110最終得到的鏈表是 0 - 0 - 0 - 1也就是數(shù)字 1000加法結(jié)果完全正確。這個(gè)例子也是我認(rèn)為每個(gè)刷這道題的人都該手動(dòng)推演一遍的用例因?yàn)樗阉腥菀壮鲥e(cuò)的點(diǎn)一網(wǎng)打盡長(zhǎng)度不等、連續(xù)進(jìn)位、最高位最終溢出產(chǎn)生新節(jié)點(diǎn)。手動(dòng)走完這一遍你對(duì)這個(gè) while 循環(huán)的信任度會(huì)提升很多面試時(shí)也能更從容地講出循環(huán)結(jié)束自動(dòng)處理了最終進(jìn)位這個(gè)結(jié)論。3.3 代碼實(shí)現(xiàn)與復(fù)雜度從復(fù)雜度角度看這個(gè)解法的時(shí)間復(fù)雜度是 O(max(m, n))其中 m 和 n 分別是兩個(gè)鏈表的長(zhǎng)度。因?yàn)檠h(huán)的每一次迭代處理一位數(shù)字迭代次數(shù)等于較長(zhǎng)的鏈表長(zhǎng)度加上可能的最后進(jìn)位多出來的一次。空間復(fù)雜度是 O(max(m, n))因?yàn)榻Y(jié)果鏈表的長(zhǎng)度大致等于較長(zhǎng)鏈表長(zhǎng)度加一。這個(gè)復(fù)雜度表現(xiàn)是這道題的最優(yōu)解。你不可能比 O(max(m, n)) 更快了因?yàn)橹辽僖闅v完兩個(gè)輸入鏈表才能完成計(jì)算?？臻g上你也不可能更省了因?yàn)楸仨氁陆ㄒ粋€(gè)鏈表來裝結(jié)果。所以如果你在面試中寫出了這個(gè)解法可以明確告訴面試官這個(gè)方案的時(shí)間和空間都已經(jīng)是最優(yōu)的這會(huì)讓你的技術(shù)溝通顯得非常專業(yè)。我提供上面的是 Python 寫法同樣思路換成 Java 也很直接class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); ListNode cur dummy; int carry 0; while (l1 ! null || l2 ! null || carry ! 0) { int v1 (l1 ! null) ? l1.val : 0; int v2 (l2 ! null) ? l2.val : 0; int total v1 v2 carry; carry total / 10; cur.next new ListNode(total % 10); cur cur.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } return dummy.next; } }兩種語言寫法結(jié)構(gòu)完全同構(gòu)。我自己做這道題的經(jīng)驗(yàn)是先用 Python 把邏輯想通再照著寫一遍 Java可以快速暴露語言層面的細(xì)節(jié)差異比如 Java 的空判斷更啰嗦但類型明確性更好。如果你正在準(zhǔn)備面試建議至少用一種語言把代碼背到能默寫的程度。4. 邊界條件攻防與測(cè)試用例設(shè)計(jì)4.1 三組必測(cè)的用例刷算法題最怕的不是不會(huì)做而是做完了不知道對(duì)不對(duì)。兩數(shù)相加的測(cè)試用例設(shè)計(jì)我建議重點(diǎn)覆蓋三種類型一種是一個(gè)數(shù)字為0的一種是兩個(gè)鏈表長(zhǎng)度差異懸殊的一種是連續(xù)進(jìn)位的。第一組用例是0 0。兩個(gè)鏈表各自只有一個(gè)節(jié)點(diǎn)值都是0。預(yù)期的輸出應(yīng)該是一個(gè)值為0的節(jié)點(diǎn)?？雌饋砗?jiǎn)單但如果你代碼里對(duì)虛擬頭節(jié)點(diǎn)的使用出了問題或者循環(huán)條件判斷失誤很容易返回一個(gè)空鏈表或者報(bào)空指針。這道用例是兜底用的先跑通它你至少能確認(rèn)整個(gè)框架是完備的。第二組用例是1 - 3 - 5 - 79 - 2也就是 7531 29 7560。這個(gè)用例重點(diǎn)檢驗(yàn)短鏈表走完后長(zhǎng)鏈表剩余部分能不能正確補(bǔ)算。我在初學(xué)階段就曾經(jīng)犯過這樣的錯(cuò)while 條件只寫了while (l1 ! null l2 ! null)導(dǎo)致短鏈表訪問到頭之后循環(huán)直接退出長(zhǎng)鏈表剩下的節(jié)點(diǎn)全被丟棄。用這個(gè)用例一跑錯(cuò)誤立刻顯現(xiàn)。正確的 while 條件是while (l1 ! null || l2 ! null)并在每次循環(huán)里對(duì)已經(jīng)為空的鏈表取 0 作為當(dāng)前位。第三組用例是9 - 9 - 91也就是 999 1。這個(gè)用例專門測(cè)試連續(xù)進(jìn)位和最高位溢出。前面我手動(dòng)推演過一次最終結(jié)果應(yīng)該是 0 - 0 - 0 - 1注意結(jié)果鏈表比兩個(gè)輸入里最長(zhǎng)的還多了一個(gè)節(jié)點(diǎn)。這一個(gè)多出來的節(jié)點(diǎn)恰恰是新手最容易丟的因?yàn)槿绻惆蜒h(huán)條件定成while (l1 ! null || l2 ! null)而不是帶上|| carry ! 0循環(huán)在 l2 走完后就停了進(jìn)位1會(huì)被遺落在循環(huán)外面代碼就錯(cuò)了。除了這三組還可以順手測(cè)一下5 5單次進(jìn)位、1 - 82中間位不進(jìn)位但高位相加產(chǎn)生進(jìn)位。這些用例都不難構(gòu)造關(guān)鍵是養(yǎng)成寫完代碼先設(shè)計(jì)測(cè)試用例再提交的習(xí)慣這在力扣刷題和真實(shí)工程里都是通用的基本功。4.2 常見錯(cuò)誤清單把我在這個(gè)題目上以及看別人提交踩過的坑匯總一份清單供大家對(duì)照自查while 條件少寫了or carry這是最高頻的錯(cuò)誤導(dǎo)致最終進(jìn)位丟失結(jié)果比正確值少一個(gè)最高位。while 條件用了and而不是or一旦某個(gè)鏈表遍歷完整個(gè)循環(huán)退出丟失長(zhǎng)鏈表的剩余節(jié)點(diǎn)。這是對(duì)循環(huán)應(yīng)該持續(xù)到什么時(shí)候理解不到位。取當(dāng)前位時(shí)報(bào)空指針在鏈表的節(jié)點(diǎn)可能為空時(shí)直接使用l1.val而不是先判斷if l1: v1 l1.val else: v1 0。創(chuàng)建結(jié)果節(jié)點(diǎn)時(shí)把total % 10和total // 10搞反取余得到的是當(dāng)前位整除得到的是進(jìn)位。這個(gè)搞反一次整個(gè)答案就是錯(cuò)的。忘了移動(dòng) cur 指針構(gòu)建鏈表時(shí)必須cur cur.next否則每次新節(jié)點(diǎn)都掛在同一個(gè)節(jié)點(diǎn)后面最后返回的鏈表只有一個(gè)節(jié)點(diǎn)。對(duì)虛擬頭節(jié)點(diǎn)的 next 判斷不準(zhǔn)應(yīng)該返回dummy.next。如果你返回dummy結(jié)果鏈表最前面會(huì)多出一個(gè)值為占位符的節(jié)點(diǎn)導(dǎo)致整體值錯(cuò)誤。在循環(huán)里重復(fù)處理進(jìn)位比如有的人在循環(huán)末尾額外寫了一個(gè)if (carry 0) { createNode(carry); }又在循環(huán)條件里加了or carry結(jié)果進(jìn)位節(jié)點(diǎn)被創(chuàng)建兩次。這份清單不是憑空列出來的每一條都對(duì)應(yīng)著我實(shí)際見過或者寫過的 bug。把這些錯(cuò)誤做成一張檢查表每次寫完代碼后逐條對(duì)照一遍比盲目反復(fù)提交試錯(cuò)要高效得多。5. 面試變體與進(jìn)階不只是兩數(shù)相加5.1 正序存儲(chǔ)怎么辦力扣題庫里有一道兩數(shù)相加 II同樣是兩數(shù)相加但數(shù)字在鏈表里是正序存儲(chǔ)的鏈表頭對(duì)應(yīng)的是最高位。這意味著你從頭開始遍歷時(shí)先遇到的是高位而不是低位不能直接套用逐位相加的流程因?yàn)檫M(jìn)位是從低位向高位傳播的而你訪問的順序恰好相反。處理正序存儲(chǔ)有兩條主流思路。一條是把兩個(gè)鏈表反轉(zhuǎn)轉(zhuǎn)換成逆序存儲(chǔ)然后按原題解法相加最后把結(jié)果再反轉(zhuǎn)回去。另一條是用兩個(gè)棧分別把兩個(gè)鏈表的節(jié)點(diǎn)值壓入彈出的時(shí)候就是低位先出等于手動(dòng)模擬了從低位到高位的訪問順序。棧方案的代碼相對(duì)簡(jiǎn)潔也能順帶展示你對(duì)棧這種后進(jìn)先出結(jié)構(gòu)的理解面試中很加分。這道變體題的考點(diǎn)在于你能不能識(shí)別出存儲(chǔ)順序影響計(jì)算順序這個(gè)核心矛盾。逆序存儲(chǔ)時(shí)計(jì)算順序和遍歷順序一致正序存儲(chǔ)時(shí)兩者相反所以要通過反轉(zhuǎn)或棧來對(duì)齊。理解了這一點(diǎn)無論題目怎么改存儲(chǔ)方式你都能快速找到解法路徑。5.2 大數(shù)相加的思路轉(zhuǎn)移兩數(shù)相加的鏈表版本本質(zhì)上是大數(shù)相加Big Integer Addition問題的一種具體表現(xiàn)形式。所謂大數(shù)就是超過語言原生整數(shù)類型范圍的長(zhǎng)整數(shù)只能用字符串、數(shù)組或鏈表來存儲(chǔ)。力扣上的字符串相加題目就是同一思路的兄弟題給你兩個(gè)用字符串表示的非負(fù)整數(shù)返回它們的和同樣不能用內(nèi)置的大整數(shù)庫。具體到實(shí)現(xiàn)上字符串相加的寫法會(huì)更短一些因?yàn)樽址梢园聪聵?biāo)訪問任意位置不像鏈表只能從頭部一個(gè)個(gè)往后遍歷。但核心邏輯一模一樣從低位往高位逐位相加維護(hù)進(jìn)位最終處理可能殘留的最高位進(jìn)位。你在兩數(shù)相加這道題里練熟的計(jì)算模式和轉(zhuǎn)移邏輯可以直接平移到字符串相加二進(jìn)制求和數(shù)組形式的加一等一大票題目上。這道題的變體訓(xùn)練價(jià)值就在這里算法題的套路不是靠死記硬背而是靠識(shí)別這類題共享同一套核心邏輯然后把核心邏輯用在不同的數(shù)據(jù)結(jié)構(gòu)外殼上。在我看來兩數(shù)相加就是理解這套邏輯最好的起點(diǎn)因?yàn)樗阎鹞幌嗉? 進(jìn)位數(shù)學(xué)模型和鏈表指針移動(dòng)這個(gè)編碼動(dòng)作結(jié)合得最干凈。5.3 遞歸解法與迭代解法的取舍兩數(shù)相加除了上述的迭代解法還有一個(gè)遞歸版本。遞歸的思路是把兩個(gè)鏈表在當(dāng)前位置相加抽象成一個(gè)函數(shù)函數(shù)里處理當(dāng)前位的加法和進(jìn)位然后遞歸調(diào)用自身處理下一個(gè)節(jié)點(diǎn)。偽代碼大致是定義一個(gè)函數(shù)add(l1, l2, carry)它計(jì)算當(dāng)前位的值創(chuàng)建對(duì)應(yīng)節(jié)點(diǎn)將節(jié)點(diǎn)的 next 指向add(l1.next, l2.next, nextCarry)的遞歸結(jié)果最后返回當(dāng)前節(jié)點(diǎn)。遞歸解法在代碼上可能顯得更高級(jí)但我個(gè)人的建議是面試中如果時(shí)間允許優(yōu)先寫迭代版本再補(bǔ)充說明遞歸思路。迭代版本沒有遞歸深度限制的問題邏輯也更直觀不容易在極端情況下爆棧。鏈表長(zhǎng)度為 n 時(shí)遞歸深度就是 n如果 n 達(dá)到幾千甚至上萬某些環(huán)境下遞歸版本會(huì)直接棧溢出。當(dāng)然理解遞歸版本對(duì)你深入理解這道題是有幫助的。遞歸解法天然體現(xiàn)了當(dāng)前節(jié)點(diǎn)的處理只依賴當(dāng)前值和下一個(gè)節(jié)點(diǎn)的處理結(jié)果這種分解思想和鏈表的遞歸定義結(jié)構(gòu)吻合。面試官如果要求你用遞歸寫你也要能寫出來。但這道題的工程實(shí)現(xiàn)上迭代是更穩(wěn)妥的默認(rèn)選擇。面試時(shí)先交一個(gè)穩(wěn)妥的答案再用討論的方式展示其他解法是我反復(fù)強(qiáng)調(diào)的面試策略。6. 刷題方法論一道鏈表題總結(jié)出的通用模板6.1 鏈表題四步走把兩數(shù)相加這道題吃透之后我建議你主動(dòng)從中總結(jié)一套做鏈表類題目的通用方法論這會(huì)比多做五道題還有價(jià)值。根據(jù)我的刷題經(jīng)驗(yàn)鏈表題大體可以拆成四步。第一步是明確遍歷的起點(diǎn)和方向。鏈表只有頭節(jié)點(diǎn)可以訪問所以幾乎所有操作都要從頭開始。如果題目要求從尾開始就要考慮反轉(zhuǎn)或者用棧。這個(gè)判斷決定了你接下來用什么結(jié)構(gòu)來配合。第二步是搞清楚每個(gè)節(jié)點(diǎn)的訪問條件。鏈表的長(zhǎng)度通常不可預(yù)知所以 while 循環(huán)的條件一般是while (node ! null)或者更復(fù)雜的至少有一個(gè)鏈表沒遍歷完的組合條件。第三步是設(shè)計(jì)節(jié)點(diǎn)操作。新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)、修改指針指向操作順序上有個(gè)鐵律先處理新節(jié)點(diǎn)和原鏈表的連接關(guān)系再移動(dòng)用于遍歷的指針順序反了會(huì)造成節(jié)點(diǎn)丟失。第四步是確認(rèn)邊界。循環(huán)結(jié)束之后通常還要檢查一下尾部是否有殘留的進(jìn)位、是否需要斷開某個(gè)指針、是否多了一個(gè)需要?jiǎng)h除的虛擬頭節(jié)點(diǎn)。這套四步法不是我憑空想出來的標(biāo)準(zhǔn)答案而是在反復(fù)寫鏈表題的過程中自己總結(jié)的檢查清單。每次遇到新鏈表題我都會(huì)先在草稿紙上把這四步的答案寫出來再動(dòng)手寫代碼。兩數(shù)相加就是練習(xí)這套方法的第一步題目用熟了之后再看合并兩個(gè)有序鏈表刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)反轉(zhuǎn)鏈表 II這些題你的恐懼感會(huì)小很多因?yàn)楣羌苁峭粋€(gè)。6.2 從這道題延伸出去的高頻題既然說了兩數(shù)相加是鏈表操作的關(guān)鍵樞紐順著這個(gè)思路往外延展有幾道高頻題和它的解法結(jié)構(gòu)非常接近我建議你按順序刷一遍。合并兩個(gè)有序鏈表幾乎是一道可以照抄兩數(shù)相加框架的題兩個(gè)鏈表的指針同時(shí)遍歷比較當(dāng)前節(jié)點(diǎn)的大小選擇小的那個(gè)接到結(jié)果鏈表上然后移動(dòng)對(duì)應(yīng)指針。不同之處在于它不需要進(jìn)位邏輯但需要處理一個(gè)鏈表走完另一個(gè)還有剩余的收尾。兩兩交換鏈表中的節(jié)點(diǎn)則是另一種風(fēng)格的鏈表操作題不新建結(jié)果鏈表而是在原鏈表上通過修改指針來交換相鄰節(jié)點(diǎn)順序。它考驗(yàn)的是對(duì)虛擬頭節(jié)點(diǎn)和指針順序的掌握很多人在這個(gè)題上畫出指針圖才能寫明白。K 個(gè)一組翻轉(zhuǎn)鏈表則是把反轉(zhuǎn)鏈表和鏈表分段兩個(gè)操作組合起來是鏈表難題的代表。它的解法骨架依然是遍歷、定位、操作、前移只是每一組的內(nèi)部處理更復(fù)雜。把這個(gè)題放在兩數(shù)相加之后去攻克是因?yàn)槟阋呀?jīng)有了一套順手的鏈表操作模板學(xué)起來會(huì)順暢得多。這些題目之間有清晰的梯度。如果兩數(shù)相加你已經(jīng)寫得非常熟練了說明你對(duì)鏈表的基本遍歷、節(jié)點(diǎn)創(chuàng)建、指針移動(dòng)已經(jīng)形成了肌肉記憶這時(shí)候再往難度高的題目上走每一步都會(huì)更穩(wěn)當(dāng)。我始終覺得刷題的數(shù)量不重要重要的是有沒有在關(guān)鍵題目上把通用的模式吃透。兩數(shù)相加就是把鏈表操作吃透的最佳起點(diǎn)這也是我寫這篇分享的初衷。