1. 從“列豎式”到“鏈表相加”一個程序員的基本功最近在幫團(tuán)隊新人做算法復(fù)盤發(fā)現(xiàn)“鏈表相加”這道題幾乎成了檢驗(yàn)基礎(chǔ)是否扎實(shí)的“試金石”。題目本身不難就是模擬兩個大數(shù)相加但鏈表的結(jié)構(gòu)特性讓很多朋友在處理進(jìn)位、對齊和結(jié)果構(gòu)建時容易手忙腳亂。網(wǎng)上題解很多但要么過于追求代碼的極致簡潔犧牲了可讀性要么步驟跳躍讓初學(xué)者看得云里霧里。今天我們不談奇技淫巧就回歸最樸素的思路——像小學(xué)列豎式計算一樣一步步拆解“鏈表相加(二)”目標(biāo)是讓你看完后不僅能寫出代碼更能透徹理解每一個操作背后的“為什么”。這道題的核心場景是給定兩個非空鏈表分別代表兩個非負(fù)整數(shù)。鏈表的每個節(jié)點(diǎn)存儲一位數(shù)字且數(shù)字是逆序存放的。比如數(shù)字123會表示為3 - 2 - 1。我們需要計算這兩個數(shù)的和并以相同的逆序鏈表形式返回結(jié)果。這實(shí)際上模擬了從個位開始相加的豎式計算過程非常直觀。理解了這個場景就成功了一半。2. 問題本質(zhì)與核心挑戰(zhàn)為什么“逆序”反而是簡化初看題目你可能會疑惑為什么要把數(shù)字逆序存儲這不是自找麻煩嗎恰恰相反這正是題目的精妙之處也是我們解題的關(guān)鍵切入點(diǎn)。2.1 “逆序”存儲的天然優(yōu)勢對齊個位在常規(guī)的十進(jìn)制加法中我們必須從個位開始相加然后處理進(jìn)位。如果鏈表是正序存儲即1 - 2 - 3代表 123那么我們需要先遍歷到鏈表末尾找到個位節(jié)點(diǎn)3這通常需要額外的數(shù)據(jù)結(jié)構(gòu)如棧來輔助或者進(jìn)行遞歸增加了空間或理解的復(fù)雜度。而逆序存儲3 - 2 - 1完美解決了這個問題。鏈表的頭節(jié)點(diǎn)直接就是數(shù)字的個位。這意味著我們可以同時從兩個鏈表的頭部開始遍歷直接進(jìn)行對應(yīng)位的相加操作天然實(shí)現(xiàn)了“個位對齊”。這極大地簡化了我們的操作邏輯。2.2 核心挑戰(zhàn)拆解三個關(guān)鍵操作環(huán)環(huán)相扣盡管思路簡化了但在代碼實(shí)現(xiàn)中我們?nèi)孕柰咨铺幚砣齻€緊密關(guān)聯(lián)的環(huán)節(jié)鏈表遍歷與位對齊兩個鏈表長度可能不同如123和4567。當(dāng)較短的鏈表遍歷完后較長鏈表剩余的部分仍需參與計算與0相加。進(jìn)位Carry的處理這是加法的核心。當(dāng)前位的和等于l1.val l2.val carry。相加后新的當(dāng)前位值是sum % 10而新的進(jìn)位值是sum / 10。這個進(jìn)位必須參與到下一位即下一個節(jié)點(diǎn)的計算中。結(jié)果鏈表的構(gòu)建我們需要在遍歷過程中動態(tài)地創(chuàng)建新的節(jié)點(diǎn)來存儲每一位的結(jié)果并將它們正確地鏈接起來。這里涉及到鏈表操作的基本功創(chuàng)建新節(jié)點(diǎn)、移動指針。這三個挑戰(zhàn)是交織在一起的任何一個環(huán)節(jié)處理不當(dāng)都會導(dǎo)致結(jié)果錯誤。接下來我們就用最清晰的步驟來搭建解決這些挑戰(zhàn)的完整邏輯框架。3. 手把手搭建解題框架從偽代碼到清晰思路在動手寫代碼之前先用自然語言和偽代碼把流程理清楚能避免很多低級錯誤。整個流程可以概括為初始化 - 循環(huán)相加 - 處理剩余進(jìn)位 - 返回結(jié)果。3.1 第一步初始化哨兵節(jié)點(diǎn)與關(guān)鍵變量這是鏈表題中非常實(shí)用的技巧。我們創(chuàng)建一個哨兵節(jié)點(diǎn)dummy node比如叫dummy它的值無關(guān)緊要通常設(shè)為0。再創(chuàng)建一個當(dāng)前指針curr初始指向dummy。為什么要用哨兵節(jié)點(diǎn)因?yàn)樗梢院喕湵眍^部的操作。無論最終結(jié)果鏈表有多少位我們都可以通過dummy.next輕松地返回真正的頭節(jié)點(diǎn)。否則你需要額外判斷第一個結(jié)果節(jié)點(diǎn)何時創(chuàng)建代碼會多出很多if分支。同時初始化進(jìn)位carry為 0并獲取兩個鏈表的頭指針l1和l2用于后續(xù)的遍歷。偽代碼表示初始化 dummy 節(jié)點(diǎn) 初始化 curr 指針指向 dummy 初始化 carry 0 初始化 p1 l1, p2 l2 (用于遍歷)3.2 第二步主循環(huán)——逐位相加與鏈表構(gòu)建這是算法的核心循環(huán)。循環(huán)繼續(xù)的條件是鏈表l1或l2還有節(jié)點(diǎn)未遍歷完或者進(jìn)位carry不為 0。注意即使兩個鏈表都遍歷完了如果最后還有進(jìn)位比如5510進(jìn)位1循環(huán)仍需繼續(xù)一次來生成最高位的1。在每一次循環(huán)中我們做以下幾件事獲取當(dāng)前位的值獲取l1和l2當(dāng)前節(jié)點(diǎn)的值。如果某個鏈表已經(jīng)遍歷完即指針為null則其對應(yīng)值視為 0。計算當(dāng)前位和與新的進(jìn)位sum val1 val2 carry。新的當(dāng)前位數(shù)值為digit sum % 10新的進(jìn)位為carry sum / 10。創(chuàng)建節(jié)點(diǎn)并鏈接用digit創(chuàng)建一個新的鏈表節(jié)點(diǎn)newNode。將curr指針的next指向newNode。然后將curr指針移動到newNode為鏈接下一個結(jié)果節(jié)點(diǎn)做準(zhǔn)備。移動輸入鏈表指針如果l1不為空則l1移向下一個節(jié)點(diǎn)l2同理。偽代碼循環(huán)體while (l1 ! null OR l2 ! null OR carry ! 0): val1 (l1 ! null) ? l1.val : 0 val2 (l2 ! null) ? l2.val : 0 sum val1 val2 carry digit sum % 10 carry sum / 10 newNode ListNode(digit) curr.next newNode curr curr.next if (l1 ! null) l1 l1.next if (l2 ! null) l2 l2.next3.3 第三步返回最終結(jié)果循環(huán)結(jié)束后整個結(jié)果鏈表已經(jīng)通過curr指針逐個鏈接在了哨兵節(jié)點(diǎn)dummy之后。因此最終的結(jié)果鏈表的頭節(jié)點(diǎn)就是dummy.next。直接返回它即可。return dummy.next這個框架邏輯清晰完全模擬了手算加法的過程。接下來我們將其轉(zhuǎn)化為具體的代碼并深入每一個細(xì)節(jié)。4. 代碼實(shí)現(xiàn)與逐行精講我們以 Java 語言為例因?yàn)槠湔Z法清晰適合表達(dá)算法邏輯。其他語言的思路完全一致。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val x; } * } */ public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 1. 初始化哨兵節(jié)點(diǎn)和指針 ListNode dummy new ListNode(0); ListNode curr dummy; int carry 0; // 2. 主循環(huán)遍歷鏈表并處理進(jìn)位 while (l1 ! null || l2 ! null || carry ! 0) { // 2.1 獲取當(dāng)前位的值空節(jié)點(diǎn)視為0 int val1 (l1 ! null) ? l1.val : 0; int val2 (l2 ! null) ? l2.val : 0; // 2.2 計算當(dāng)前位和與進(jìn)位 int sum val1 val2 carry; int digit sum % 10; // 當(dāng)前位結(jié)果 carry sum / 10; // 新的進(jìn)位 // 2.3 創(chuàng)建新節(jié)點(diǎn)并鏈接到結(jié)果鏈表 ListNode newNode new ListNode(digit); curr.next newNode; curr curr.next; // 移動curr到新節(jié)點(diǎn) // 2.4 移動輸入鏈表的指針 if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 3. 返回結(jié)果鏈表的頭節(jié)點(diǎn) return dummy.next; } }逐行精講與避坑點(diǎn)第12行while循環(huán)條件(l1 ! null || l2 ! null || carry ! 0)。這是最容易出錯的地方之一。必須把carry ! 0也作為循環(huán)條件?？紤]用例5 5鏈表為5 - null和5 - null。第一輪循環(huán)后l1和l2都為空了但carry為 1。如果沒有這個條件循環(huán)會提前結(jié)束丟失最高位的1結(jié)果變成0顯然是錯誤的。第15、16行 空值判斷使用三元運(yùn)算符安全地獲取節(jié)點(diǎn)值。這是處理鏈表長度不一致的關(guān)鍵。當(dāng)l1或l2先遍歷完時后續(xù)計算中其對應(yīng)值就一直是 0。第19、20行 進(jìn)位計算digit sum % 10和carry sum / 10。這是十進(jìn)制加法的標(biāo)準(zhǔn)操作。注意carry只會是 0 或 1因?yàn)閮蓚€一位數(shù)0-9加上進(jìn)位0或1最大和是99119所以進(jìn)位最大為1。第23、24行 鏈表操作curr.next newNode; curr curr.next;這是單鏈表尾部插入的標(biāo)準(zhǔn)操作。一定要先鏈接再移動curr指針。順序反了會導(dǎo)致鏈表斷裂。第27、28行 移動輸入指針在移動l1和l2之前一定要先判斷它們是否為空。對空指針調(diào)用next會導(dǎo)致NullPointerException。這套代碼的時間復(fù)雜度是O(max(m, n))其中 m 和 n 分別是兩個鏈表的長度。我們只需要遍歷較長的鏈表一次?？臻g復(fù)雜度是O(max(m, n))主要用于存儲結(jié)果鏈表不包括輸入鏈表。新建的鏈表長度最多為max(m, n) 1因?yàn)榭赡苡蓄~外進(jìn)位。5. 從“正確”到“健壯”邊界情況與測試用例設(shè)計能通過題目給的示例只是第一步。一個健壯的算法必須能處理各種邊界情況。對于鏈表相加以下幾類測試用例必須考慮常規(guī)不等長[1,2,3] [4,5,6,7](即1237654)。測試進(jìn)位在不同長度下的傳遞。有連續(xù)進(jìn)位[9,9,9] [1](即9991)。這是最經(jīng)典的連續(xù)進(jìn)位測試最終結(jié)果是[0,0,0,1]。最后產(chǎn)生額外進(jìn)位[5] [5](即55)。測試循環(huán)條件中carry ! 0的必要性。一個鏈表為空[] [1,2,3]。測試空指針處理。通常題目說明是非空鏈表但養(yǎng)成處理空值的習(xí)慣很好。大數(shù)兩個很長的鏈表相加。測試程序在常規(guī)整數(shù)類型如int下的正確性。實(shí)際上因?yàn)槊课粏为?dú)計算所以不會出現(xiàn)整型溢出問題這是鏈表表示大數(shù)的優(yōu)勢。在本地調(diào)試時建議你寫出完整的測試代碼包括鏈表的構(gòu)建和打印函數(shù)。例如public static void main(String[] args) { Solution solution new Solution(); // 測試用例 342 465 807 ListNode l1 new ListNode(2); l1.next new ListNode(4); l1.next.next new ListNode(3); ListNode l2 new ListNode(5); l2.next new ListNode(6); l2.next.next new ListNode(4); ListNode result solution.addTwoNumbers(l1, l2); // 打印結(jié)果鏈表應(yīng)為 7 - 0 - 8 printList(result); } static void printList(ListNode head) { while (head ! null) { System.out.print(head.val - ); head head.next; } System.out.println(null); }通過運(yùn)行這些測試用例你可以直觀地驗(yàn)證算法的正確性并加深對流程的理解。6. 常見誤區(qū)與思維深化對比其他解法在理解了上述標(biāo)準(zhǔn)解法后我們來看看初學(xué)者容易陷入的幾個誤區(qū)以及一些“炫技”解法的本質(zhì)。6.1 誤區(qū)一先反轉(zhuǎn)鏈表再相加最后再反轉(zhuǎn)這是最容易想到的“笨辦法”。因?yàn)轭}目是逆序存儲有人會覺得不習(xí)慣就想先反轉(zhuǎn)鏈表變成正序然后用更“自然”的方式相加最后再把結(jié)果反轉(zhuǎn)回去。比如反轉(zhuǎn)l1得到L1。反轉(zhuǎn)l2得到L2。正序相加L1和L2這個過程更復(fù)雜因?yàn)橐獜奈膊繉R。反轉(zhuǎn)結(jié)果鏈表。這種方法的問題在于復(fù)雜度增加需要寫兩個完整的鏈表反轉(zhuǎn)函數(shù)?？臻g開銷反轉(zhuǎn)操作通常是原地進(jìn)行但增加了思維復(fù)雜度和出錯概率。多此一舉題目設(shè)計的逆序存儲本意就是讓你直接從頭開始加。這種解法沒有理解題目的意圖。6.2 誤區(qū)二使用棧Stack來輔助思路是遍歷鏈表將值壓入棧中。這樣棧頂就是數(shù)字的最高位。然后同時彈出兩個棧的元素進(jìn)行相加。這本質(zhì)上是在模擬正序相加。問題在于空間復(fù)雜度高需要額外的 O(mn) 空間來存儲棧。代碼更復(fù)雜需要處理兩個?？赡転榭盏那闆r以及結(jié)果鏈表是正序還是逆序的問題通常需要頭插法效率低。6.3 遞歸解法另一種優(yōu)雅的視角除了迭代遞歸也能解決這個問題而且代碼非常簡潔體現(xiàn)了另一種思維方式。public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return add(l1, l2, 0); } private ListNode add(ListNode l1, ListNode l2, int carry) { // 遞歸基如果兩個鏈表都為空且無進(jìn)位則返回null if (l1 null l2 null carry 0) { return null; } // 計算當(dāng)前位的和與進(jìn)位 int val1 (l1 ! null) ? l1.val : 0; int val2 (l2 ! null) ? l2.val : 0; int sum val1 val2 carry; int digit sum % 10; int newCarry sum / 10; // 創(chuàng)建當(dāng)前節(jié)點(diǎn) ListNode node new ListNode(digit); // 遞歸計算下一個節(jié)點(diǎn) ListNode next1 (l1 ! null) ? l1.next : null; ListNode next2 (l2 ! null) ? l2.next : null; node.next add(next1, next2, newCarry); return node; }遞歸解法的分析優(yōu)點(diǎn)代碼極其簡潔邏輯清晰直接表達(dá)了“當(dāng)前位計算 后續(xù)位計算”的語義。缺點(diǎn)存在遞歸棧的空間開銷最壞情況空間復(fù)雜度也是 O(max(m, n))。對于非常長的鏈表如數(shù)萬節(jié)點(diǎn)有棧溢出的風(fēng)險。適用場景在面試中如果你能清晰解釋遞歸思路這是一個很好的加分項體現(xiàn)了對問題不同角度的理解。但在生產(chǎn)環(huán)境中處理超長數(shù)據(jù)時迭代法更穩(wěn)妥。對比下來我們最初講解的迭代哨兵節(jié)點(diǎn)的方法在時間復(fù)雜度、空間復(fù)雜度、代碼可讀性和健壯性上取得了最好的平衡是實(shí)際開發(fā)中最推薦的做法。7. 舉一反三鏈表加法的變體與擴(kuò)展掌握了基礎(chǔ)版本我們可以思考一些變體問題這能極大地鍛煉你的算法遷移能力。7.1 變體一鏈表正序存儲相加如果鏈表是正序存儲的即1-2-3表示 123你該如何計算這就是 LeetCode 上的另一道題。此時個位在鏈表尾部我們無法直接對齊。常見思路使用棧遍歷鏈表將值壓入棧。這樣兩個棧的棧頂都是個位。然后同時出棧相加構(gòu)建結(jié)果鏈表注意此時構(gòu)建的結(jié)果是逆序的可能需要再反轉(zhuǎn)或者使用頭插法。遞歸到尾部利用遞歸“歸”的過程從個位開始計算。遞歸函數(shù)返回(節(jié)點(diǎn), 進(jìn)位)在回溯過程中構(gòu)建鏈表。這種方法寫起來巧妙但理解成本較高。先反轉(zhuǎn)再相加這就是我們前面提到的“笨辦法”但在此場景下反而成了直接解法先反轉(zhuǎn)兩個輸入鏈表變成逆序然后用我們剛學(xué)會的方法相加最后再反轉(zhuǎn)結(jié)果鏈表變回正序。7.2 變體二多個鏈表相加如果給你一個鏈表數(shù)組ListNode[] lists需要計算所有鏈表代表數(shù)字的總和。思路可以有兩種順序兩兩相加初始化結(jié)果鏈表為lists[0]然后讓結(jié)果鏈表與lists[1]相加得到新結(jié)果再與lists[2]相加以此類推。時間復(fù)雜度是 O(k * n)k是鏈表數(shù)量n是平均長度。并行位相加模擬豎式計算同時處理所有鏈表在同一“位”上的數(shù)字。這需要維護(hù)一個指針數(shù)組并處理更復(fù)雜的進(jìn)位。時間復(fù)雜度是 O(k * n)但常數(shù)項可能更小。7.3 擴(kuò)展其他進(jìn)制的鏈表相加如果不是十進(jìn)制而是二進(jìn)制、八進(jìn)制或任意進(jìn)制b呢算法框架完全不變只需要修改進(jìn)位計算規(guī)則當(dāng)前位結(jié)果digit sum % b新的進(jìn)位carry sum / b代碼只需要改動兩行這體現(xiàn)了算法核心邏輯的通用性。鏈表相加雖然是一道中等難度題但它完美融合了鏈表基本操作、數(shù)學(xué)模擬和邊界條件處理。我見過很多候選人因?yàn)楹雎宰詈蟮倪M(jìn)位或者鏈表指針操作失誤在這道題上翻車。把這道題吃透不僅能讓你在面試中從容應(yīng)對更能夯實(shí)你對鏈表這一基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的理解以及培養(yǎng)嚴(yán)謹(jǐn)?shù)木幊趟季S——處理進(jìn)位就像處理現(xiàn)實(shí)項目中的狀態(tài)傳遞每一步都必須清晰無誤。下次再遇到它希望你能自信地寫出清晰、健壯、高效的代碼。