LeetCode刷題實(shí)戰(zhàn)2：用鏈表模擬加法
廢話不多說(shuō)，讓我們一起來(lái)看看題目吧，今天要講的是一道經(jīng)典的算法題，雖然不難，但是很有意思，我們一起來(lái)看下題目：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.?
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
https://leetcode.com/problems/two-sum/
翻譯
給定兩個(gè)非空的鏈表，代表兩個(gè)非負(fù)整數(shù)。這兩個(gè)整數(shù)都是倒敘存儲(chǔ)，要求返回一個(gè)鏈表，表示這兩個(gè)整數(shù)的和。
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
解答
題目不難理解，思路也很容易想明白，其實(shí)就是模擬小學(xué)生打豎式計(jì)算加減的方法，來(lái)計(jì)算兩個(gè)整數(shù)的加和。但是既然是加法，就可能涉及進(jìn)位，比如兩個(gè)兩位數(shù)的和可能是一個(gè)三位數(shù)。還有一個(gè)難點(diǎn)是需要使用鏈表來(lái)實(shí)現(xiàn)，涉及鏈表，編碼的復(fù)雜度會(huì)更大一些。
在開始編碼之前，我們先仔細(xì)觀察樣例：
while (l1 || l2) {if (l1) l1 = l1->next;if (l2) l2 = l2->next;}
手動(dòng)創(chuàng)建鏈表也并不復(fù)雜，我們首先創(chuàng)建一個(gè)鏈表的節(jié)點(diǎn)，然后依次往節(jié)點(diǎn)后方插入節(jié)點(diǎn)即可。鏈表插入的方式也很簡(jiǎn)單，假設(shè)當(dāng)前的節(jié)點(diǎn)是cur，待插入的節(jié)點(diǎn)是node，那么我們只需要用cur.next指向node，然后將cur賦值成node即可，如圖：
cur->next = node;cur = node;
計(jì)算產(chǎn)生的進(jìn)位問(wèn)題就更簡(jiǎn)單了，由于我們是按位來(lái)計(jì)算加法，所以我們可以用一個(gè)變量標(biāo)記之前位是否發(fā)生進(jìn)位。如果發(fā)生，那么當(dāng)前的計(jì)算結(jié)果加一。因?yàn)榧臃ㄓ?jì)算，最多的結(jié)果只能達(dá)到19（兩位9再加上之前進(jìn)位），所以進(jìn)位最多只會(huì)增加1。最后，再判斷一下當(dāng)前位計(jì)算的結(jié)果是否產(chǎn)生進(jìn)位即可。
int ret = l1->val + l2->val;if (exceed) ret++;if (ret > 9) {ret -= 10;exceed = true;}else exceed = false;
最后，我們只需要把上述說(shuō)到的三點(diǎn)結(jié)合起來(lái)，就可以寫出代碼了。如果coding還是有困難，可以在公眾號(hào)回復(fù)LeetCode2，獲取代碼。
還沒有結(jié)束，在大多數(shù)語(yǔ)言當(dāng)中，int都是有范圍的。一般是32個(gè)二進(jìn)制位，如果是int64則是64個(gè)二進(jìn)制位。這是和計(jì)算機(jī)CPU的帶寬是有關(guān)的，那有沒有想過(guò)，超過(guò)64位二進(jìn)制能表示的整數(shù)應(yīng)該怎么辦呢？
其實(shí)就是用類似本題當(dāng)中的方法，通過(guò)鏈表將每一位串聯(lián)起來(lái)，在計(jì)算加減乘除的時(shí)候，則是像人工打豎式那樣去計(jì)算。這種算法稱為高精度。感興趣的同學(xué)，可以自行搜索，以后有機(jī)會(huì)，會(huì)在之后的文章里更新。
希望大家都能有所收獲，如果喜歡本文，麻煩順手轉(zhuǎn)發(fā)或者點(diǎn)擊下方“在看”。
上期推文：
LeetCode刷題實(shí)戰(zhàn)1：在數(shù)組上遍歷出花樣
