1. 先聊題目為什么這道題能進LeetCode前100LeetCode第2題“兩數(shù)相加”算是鏈表入門的基礎(chǔ)題了正好在LeetCode熱門100題榜單里。很多刷題黨把它當(dāng)成“鏈表第一題”來做因為它不像反轉(zhuǎn)鏈表那樣純考指針操作也不像合并有序鏈表那樣有明確的分治背景它把數(shù)學(xué)加法中“逐位相加、逢十進一”的過程原封不動地搬到了鏈表上。我第一次刷這道題時其實是先栽了跟頭的。當(dāng)時習(xí)慣用數(shù)組思維想著把兩個鏈表的數(shù)字先取出來轉(zhuǎn)成整型相加完了再轉(zhuǎn)回鏈表代碼寫到一半發(fā)現(xiàn)樣例測試沒問題一交就開始報錯。再看一眼題目描述里面有一行小字鏈表長度可能超過64位整數(shù)的表示范圍。也就是說這條路在工程上根本走不通。后來才明白這道題的真實考點是“手寫豎式加法”不是“讓你調(diào)BigInteger庫”。先說清楚這道題適合誰正在看鏈表基礎(chǔ)的人、準(zhǔn)備面試需要練手寫數(shù)據(jù)結(jié)構(gòu)的人、想搞明白遞歸和迭代邊界怎么處理的人都值得把它吃透。它本身不復(fù)雜但里面包含的鏈表遍歷、進位維護、哨兵節(jié)點使用、邊界條件收尾都是后續(xù)做中等難度鏈表題比如兩數(shù)相加II、合并K個升序鏈表直接要用的底層能力。順便提一句LeetCode周賽430我剛打完里面也有一道和“按位處理進位”思路非常像的題。那些題表面是硬模擬底層全是這道題的變形。2. 題目本質(zhì)逆序存儲反而幫了大忙2.1 輸入格式到底在表達什么題目給的鏈表頭節(jié)點是數(shù)字的最低位也就是說鏈表是逆序存數(shù)的。比如數(shù)字342在鏈表里是 2 - 4 - 3頭節(jié)點存?zhèn)€位。這個設(shè)定剛看會覺得別扭因為平時寫數(shù)字都是從高位往低位讀。但換成豎式加法想想就順了我們小學(xué)列豎式算加法是不是從個位開始一位一位往左加鏈表頭節(jié)點存?zhèn)€位正好讓我們從頭節(jié)點開始逐位相加時天然就是“從低位往高位”推進完全不需要先反轉(zhuǎn)鏈表。遇到一個數(shù)據(jù)結(jié)構(gòu)設(shè)計先別急著否定它想想它在為什么場景服務(wù)。逆序鏈表這個設(shè)計是專門為“加法進位從左往右傳遞”服務(wù)的。2.2 為什么數(shù)組/整數(shù)轉(zhuǎn)換方案必然炸掉很多人第一反應(yīng)是遍歷兩個鏈表把數(shù)字拼出來再相加最后轉(zhuǎn)回鏈表。這個思路在數(shù)字很小的時候確實能過但題目里明確說了鏈表長度可以很長長度超過64位甚至更長時64位整數(shù)撐不住超大數(shù)換算成字符串做加法又回到了手寫豎式的老路就算語言支持大數(shù)比如Python的int面試官也不會滿意因為這不是考你語言特性是考鏈表操作能力轉(zhuǎn)換過程本身要遍歷兩遍、構(gòu)建一遍時間空間都虧。所以這道題的標(biāo)準(zhǔn)解法就是模擬豎式加法同時遍歷兩個鏈表每輪取兩個節(jié)點的值加上上一位的進位算出當(dāng)前位的值和下一位的進位生成新節(jié)點掛到結(jié)果鏈表上。2.3 核心狀態(tài)其實只有兩個梳理一下整個過程每一輪迭代的核心就兩件事當(dāng)前位的數(shù)字是多少要不要往下一個節(jié)點進位。當(dāng)前位數(shù)字等于 (p.val q.val carry) 對10取余進位值等于 (p.val q.val carry) 除以10取整。這里的carry只能是0或1因為兩個一位數(shù)相加最高不會超過99119所以進位最多是1。這個“最多進1”的特性讓代碼判斷變得特別簡單你甚至不需要考慮carry大于1的復(fù)雜情況。3. 迭代解法從第一版到能AC的完整過程3.1 骨架代碼怎么搭先定義結(jié)果鏈表的頭和尾。用哨兵節(jié)點dummy head是最穩(wěn)妥的做法好處是即使結(jié)果鏈表一個節(jié)點都還沒有你也能通過 dummy.next 訪問到頭節(jié)點不用為判空邏輯寫多余分支。每一輪循環(huán)的標(biāo)準(zhǔn)步驟如果p不為空取p.val如果q不為空取q.val算sum pVal qVal carry當(dāng)前位數(shù)字存到新節(jié)點掛到結(jié)果鏈表尾部更新carry sum / 10移動p和q到各自的下一個節(jié)點如果有。循環(huán)結(jié)束條件有兩個p和q都為空且carry為0。注意是“且”如果p和q遍歷完了但carry還是1說明最高位還有一個進位比如 5 5 10結(jié)果鏈表應(yīng)該多出一個1節(jié)點。這是最經(jīng)典的遺漏點后面我會專門講。3.2 代碼逐行拆解以Java為例我給出一個能直接AC的版本并解釋每一段在干嘛/** * 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; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // dummyHead哨兵節(jié)點避免結(jié)果鏈表為空時的特殊判斷 ListNode dummyHead new ListNode(0); ListNode tail dummyHead; int carry 0; // l1和l2只要有一個沒走完就繼續(xù)循環(huán) while (l1 ! null || l2 ! null) { int x (l1 ! null) ? l1.val : 0; int y (l2 ! null) ? l2.val : 0; int sum x y carry; // 更新進位sum 10 時 carry 1否則 0 carry sum / 10; // 當(dāng)前位數(shù)字sum % 10 tail.next new ListNode(sum % 10); tail tail.next; if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 最高位如果還有進位需要補一個節(jié)點 if (carry 0) { tail.next new ListNode(carry); } return dummyHead.next; } }這段代碼的思路非常直接兩個鏈表同時向前推進誰短了誰就補0直到兩個都走完最后檢查有沒有多余進位。你會發(fā)現(xiàn)它幾乎沒有復(fù)雜分支原因就是逆序鏈表讓“對齊低位”這件事變成了自然行為。每種語言寫起來差不太多Python版本可以這樣# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 s v1 v2 carry cur.next ListNode(s % 10) carry s // 10 cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.nextPython的寫法有個細節(jié)while循環(huán)條件是l1 or l2 or carry這樣把“最后進位”也合并進了循環(huán)代碼更簡潔。3.3 時間復(fù)雜度與空間復(fù)雜度時間O(max(m, n))m和n是兩個鏈表的長度。因為每輪循環(huán)處理一個節(jié)點循環(huán)次數(shù)等于較長鏈表的長度加上可能的最后一次進位?？臻g如果不算輸出結(jié)果占用的空間額外空間是O(1)只用了幾個指針變量。但如果把結(jié)果鏈表本身算進去是O(max(m, n))。面試時被問到復(fù)雜度是標(biāo)準(zhǔn)回答主要是O(max(m,n))的時間因為每個節(jié)點最多訪問一次?？臻g要看你算不算輸出鏈表通常答“額外空間O(1)”就可以了。4. 遞歸解法另一種等價的思考方式4.1 遞歸的拆法迭代是“從低位到高位不斷生成節(jié)點”遞歸則是把“當(dāng)前位的加法”和“剩余節(jié)點相加的結(jié)果”拆開。每層遞歸只做一件事計算當(dāng)前位的和與進位遞歸計算剩余部分的和把當(dāng)前位的新節(jié)點指向剩余部分的結(jié)果。遞歸終止條件兩個鏈表都為空且進位為0返回null。這里同樣要把進位納入終止條件不然會丟掉最高位的1。4.2 遞歸代碼示例class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return helper(l1, l2, 0); } private ListNode helper(ListNode l1, ListNode l2, int carry) { if (l1 null l2 null carry 0) { return null; } int x (l1 ! null) ? l1.val : 0; int y (l2 ! null) ? l2.val : 0; int sum x y carry; ListNode node new ListNode(sum % 10); // 遞歸處理剩余部分注意null節(jié)點的next也傳null ListNode nextL1 (l1 ! null) ? l1.next : null; ListNode nextL2 (l2 ! null) ? l2.next : null; node.next helper(nextL1, nextL2, sum / 10); return node; } }遞歸版的代碼看著更短但有兩處容易出錯終止條件漏掉carry傳下一層遞歸時忘了先把l1和l2判空再取next。我的建議遞歸版適合理解思路面試手寫推薦迭代版。因為遞歸如果遞歸深度很大鏈表很長會有棧溢出的風(fēng)險。雖然LeetCode的測試數(shù)據(jù)不會把你逼到棧溢出但“遞歸深度等于鏈表長度”這個事實和迭代O(1)額外棧空間相比是要扣分的點。5. 邊界情況與測試用例這里才是真正的分水嶺5.1 實際寫代碼最容易翻車的地方第一個坑是最高位進位丟失。輸入 5 - 和 5 -正確輸出應(yīng)該是 0 - 1。如果你最后的if (carry 0)忘了寫或者把while循環(huán)條件寫成了 l1 ! null l2 ! null就會丟掉那個1。很多新手把鏈表的遍歷習(xí)慣帶進來了習(xí)慣性寫成“兩個鏈表都非空才循環(huán)”結(jié)果一個是空一個非空時直接漏掉了剩余部分。正確寫法是“只要有一個非空就循環(huán)”空缺位補0。第二個坑是兩個鏈表長度不一致時短鏈表走了就不再動了。常見錯誤是只移動p不移動q或者移動時沒判空。l1或l2可能已經(jīng)null取val前不判空會直接NullPointerException。第三個坑是鏈表自帶的節(jié)點定義別改比如LeetCode的ListNode構(gòu)造函數(shù)有帶next和不帶next兩種用的時候注意別把構(gòu)造簽名寫錯。有些同學(xué)喜歡自己封裝一個“創(chuàng)建鏈表”的工具函數(shù)本地測試用著方便提交時別忘了刪掉和題目無關(guān)的類。5.2 值得測試的用例集合刷題不是提交AC就完事真正吃透一道題建議把這幾種用例都跑一遍基本情況2 - 4 - 3 和 5 - 6 - 4結(jié)果 7 - 0 - 8長度不一致1 - 8 和 0結(jié)果 1 - 8結(jié)果變長9 - 9 - 9 和 1結(jié)果 0 - 0 - 0 - 1空鏈表一個鏈表為null另一個正常結(jié)果應(yīng)該直接等于正常鏈表當(dāng)然正常遍歷也能出來全是00 和 0結(jié)果 0大數(shù)溢出測試構(gòu)造一個30位的鏈表驗證結(jié)果和手寫豎式一致。這些用例覆蓋了“有沒有進位”“長度相同還是不同”“鏈表空不空”三種維度?；具壿嫴粡?fù)雜的題最大的敵人就是這些細節(jié)。6. 進階如果鏈表是正序存儲還能這么寫嗎6.1 正序場景下的新問題LeetCode里有道姐妹題“兩數(shù)相加II”鏈表是正序存儲數(shù)字的342存成3 - 4 - 2頭節(jié)點是最高位。那題目就沒這么幸福了因為從最高位開始加如果低位有進位你是沒法提前知道的。正序鏈表相加的常規(guī)解法有三種先反轉(zhuǎn)兩個鏈表按逆序相加最后再反轉(zhuǎn)結(jié)果用兩個棧分別存儲兩個鏈表的節(jié)點彈出時從低位開始加結(jié)果用頭插法構(gòu)建遞歸處理先遞歸到底后再回溯相加但進位問題需要額外處理。思路1最容易理解也最好寫。思路2避免了反轉(zhuǎn)鏈條的額外操作邏輯上更直接一點。無論哪種都比原題多了一步“解決順序問題”的功夫。6.2 從這道題能沉淀出的通用能力“兩數(shù)相加”這道題最有價值的地方不是讓你背下這段代碼而是讓你理解鏈表作為“按位處理”載體時的天然優(yōu)勢哨兵節(jié)點如何幫你省掉麻煩的判空分支循環(huán)條件和邊界狀態(tài)carry要一起參與判斷短鏈表的缺失位用0補齊比寫一堆if else更優(yōu)雅。這些思路在后來的合并兩個有序鏈表、分隔鏈表、K個一組翻轉(zhuǎn)鏈表、甚至樹相關(guān)的遞歸題里都能復(fù)用到。鏈表題刷多了你會發(fā)現(xiàn)所謂的“不同類型的題”底層邏輯其實高度相似都是“游標(biāo)移動 鏈接關(guān)系維護 邊界條件收尾”。7. 測試代碼與本地調(diào)試技巧7.1 構(gòu)造鏈表和打印鏈表的通用模板LeetCode上你只需要寫Solution類不需要處理輸入輸出。但本地調(diào)試時沒有main方法很難受。我每次刷鏈表題都會在本地建一個工具類包含兩個方法一個是根據(jù)數(shù)組生成鏈表一個是打印鏈表。public class ListNodeUtil { public static ListNode buildList(int[] arr) { ListNode dummy new ListNode(0); ListNode cur dummy; for (int val : arr) { cur.next new ListNode(val); cur cur.next; } return dummy.next; } public static String printList(ListNode head) { StringBuilder sb new StringBuilder(); while (head ! null) { sb.append(head.val).append( - ); head head.next; } sb.append(null); return sb.toString(); } }有了這兩個工具測試用例就寫得很舒服public class TestAddTwoNumbers { public static void main(String[] args) { Solution solution new Solution(); ListNode l1 ListNodeUtil.buildList(new int[]{2, 4, 3}); ListNode l2 ListNodeUtil.buildList(new int[]{5, 6, 4}); ListNode result solution.addTwoNumbers(l1, l2); System.out.println(ListNodeUtil.printList(result)); ListNode l3 ListNodeUtil.buildList(new int[]{9, 9, 9}); ListNode l4 ListNodeUtil.buildList(new int[]{1}); ListNode result2 solution.addTwoNumbers(l3, l4); System.out.println(ListNodeUtil.printList(result2)); } }7.2 本地調(diào)試時注意LeetCode不背鍋的坑有時候在本地跑得好好的一提交就編譯錯誤原因多半是main函數(shù)和工具類寫在了同一個文件里但LeetCode后臺只認Solution類自己定義的ListNode類名和LeetCode內(nèi)建的類名沖突重復(fù)定義了用了題目沒引入的包比如Arrays類的import漏了。建議的做法在本地建一個單獨的項目把ListNode、Solution、工具類分開文件存。提交時只復(fù)制Solution類的內(nèi)容到LeetCode編輯框就不會出錯。8. 我的一點心得這道題我已經(jīng)刷過不止一遍了。第一遍是用迭代解法AC完就忘第二遍是面試前回爐突然發(fā)現(xiàn)自己第一次寫的時候居然還在“先轉(zhuǎn)數(shù)組再相加”屬于典型的思維偷懶。后來把遞歸版、正序版、甚至用棧實現(xiàn)的版本都寫了一遍才真正理解它的內(nèi)核就是“進位模擬”。刷題這事的規(guī)律是一開始覺得每道題都是新題刷到一定量之后會覺得都是老朋友。兩數(shù)相加這道題可以說是我在鏈表這塊的啟蒙題。你把它徹底弄明白之后再去做合并K個升序鏈表、K個一組翻轉(zhuǎn)鏈表、重排鏈表會明顯感覺到思想上更順了。最后分享一個我常用的刷題習(xí)慣一道簡單題AC之后別急著下一道試著改一改條件再做一遍。比如這道題你可以自己問自己“如果鏈表是正序呢”“如果要求原地修改不能新建鏈表呢”“如果數(shù)字不是10進制而是2進制呢”這幾個變體一練你對這道題的掌握就遠不止“做過一遍”了。LeetCode刷題的價值從來不在數(shù)量在你能不能把一個通用模式真正吃透。