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写进链表里。