1 题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头

示例

1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

2 解题

使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

就像我们在纸上计算两个数字的和那样，首先从最低有效位也就是列表$l1$和 $l2$的表头开始相加。由于每位数字都应当处于$0…9$的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，$5+8=13$ 。在这种情况下，我们会将当前位的数值设置为$3$，并将进位$carry=1$带入下一次迭代。进位$carry$必定是$0$或$1$，这是因为两个数字相加（考虑到进位）可能出现的最大和为$9+9+1=19$ 。

基于上述分析，伪代码如下：

  • 将当前节点初始化为返回列表的哑节点。

  • 将进位$carry$初始化为1。

  • 将$p$和$q$分别初始化为列表$l1$和$l2$的头部。

  • 遍历列表$l1$和$l2$直至到达它们的尾端。

  • 将$x$设为节点$p$的值。如果$p$已经到达$l1$的末尾，则将其值设置为$0$。

  • 将$y$设为节点$q$的值。如果$q$已经到达$l2$的末尾，则将其值设置为$0$。

  • 设定$sum=x+y+carry$。

  • 更新进位的值,$carry=sum/10$。

  • 创建一个数值为 ( $sum \ mod \ 10$ ) 的新节点，并将其设置为当前节点的下一个节点，然后将当前节点前进到下一个节点。

  • 同时，将$p$和$q$前进到下一个节点。

  • 检查$carry = 1$是否成立，如果成立，则向返回列表追加一个含有数字$1$ 的新节点。返回哑节点的下一个节点。

请注意，我们使用哑节点来简化代码。如果没有哑节点，则必须编写额外的条件语句来初始化表头的值。

同时需要注意的以下情况：

1
2
3
4
5

测试用例：
l1 = [0, 1]
l2 = [0, 1, 2]

说明：当一个列表比另一个列表长时。

1
2
3
4
5

测试用例：
l1 = []
l2 = [0, 1]

说明：当一个列表为空时，即出现空列表。

1
2
3
4
5

测试用例：
l1 = [9, 9]
l2 = [1]

说明：求和运算最后可能出现额外的进位，这一点很容易被遗忘

综上，得到的解题代码（cpp）如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
    ListNode* ret = new ListNode(0);	//创建一个哑节点
    //创建两个链表指针用于遍历l1与l2
    ListNode* p = l1; 
    ListNode* q = l2;
    //用于遍历结果列表的链表指针
    ListNode* curr = ret;
    int carry = 0;						//进位先初始化为0
    if (l1 == NULL || l2 == NULL)		//若一个链表为空的情况
    {
        ret = NULL;
        return ret;
    }
    while (p != NULL || q != NULL)		// 遍历完l1与l2
    {
        //若其中一个节点遍历完成，将后续在该链表的值都置为0
        int x = (p != NULL) ? p->val : 0;
        int y = (q != NULL) ? q->val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
		
        //注意curr是从哑节点开始的，它的下个节点存储的才是结果位数据
        curr->next = new ListNode(sum % 10);//创建数值为（sum%10）的节点存储当前结果位数据
        //移动链表指针，准备进行下一位的计算
        curr = curr->next;
        if (p != NULL) p = p->next;
        if (q != NULL) q = q->next;
    }
    //遍历完检查是否还有存在进位，若有，再创建一个为1的新节点追加至后面
    if (carry > 0)
    {
        curr->next = new ListNode(carry);
    }
    return ret->next;
}

复杂度分析：

  • 时间复杂度：$O(\max(m,n))$。假设 $m$ 和 $n$分别表示$l1$和$l2$的长度，上面的算法最多重复$\max(m,n)$次。

  • 空间复杂度:$O(\max(m,n))$,新列表的长度最多为$\max(m,n)+1$