2.3 實例2：二進制相加

給定兩個二進制字符串，返回它們的和（也是一個二進制字符串），例如：

輸入：a="11"，b="1"

輸出："100"

說明：輸入字符串均為非空，并且僅包含字符1或0。

解題思路：這道題主要考查字符串操作的基礎知識，通過從右向左逐位相加得到數值。首先獲取每個數對應位置上的數字，比如element_a和element_b，需要定義一個進位值carry。計算二進制的加法可以利用（element_a+element_b+carry）÷2，其余數就是當前位置的值，商就是傳遞給下一個位置的carry值。當然，這里需要注意兩個數的長度可能不一樣。最后需要考慮carry值是否為1，如果為1，則需要把1添加到結果最前面的位置。二進制相加示意圖如圖2-1所示。

這里我們利用輔助變量carry，初始化為0。

第一步：利用1+0+carry=1，1%2=1，商為0，填充第一位為1，同時更新carry=0；

第二步：利用1+1+carry=2，2%2=0，商為1，填充第二位為0，同時更新carry=1；

第三步：利用1+1+carry=3，3%2=1，商為1，填充第三位為1，同時更新carry=1；

第四步：利用0+1+carry=2，2%2=0，商為1，填充第四位為0，同時更新carry=1；

第五步：利用1+0+carry=2，2%2=0，商為1，填充第五位為0，同時更新carry=1；

第六步：利用1+carry=2，2%2=0，商為1，填充第五位為0，同時更新carry=1；

第七步：查看carry值是否為1，如果是，則把1添加到最前面。

復雜度分析：時間復雜度為O（n），空間復雜度為O（1）。

與這個問題比較類似的是Leetcode第445題，如下：

輸入：（7->2->4->3）+（5->6->4）

輸出：7->8->0->7

該題只需把兩個相加的數放在兩個鏈表里面，解法和上例一樣，每個數字從鏈表里取出。首先通過不斷讀取鏈表里的值，把它轉成一個數，比如（7->2->4->3）可以轉成7243，（5->6->4）轉成564，然后把7243+564加起來，得到7807。最后創建一個新的鏈表，把7807寫進鏈表里。