给你两个非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
输入与输出示例如下1所示:
示例 1: 输入:l1 = [2,4,3], l2 = [5,6,4] 输出:[7,0,8] 解释:342 + 465 = 807.
示例 2: 输入:l1 = [0], l2 = [0] 输出:[0]
示例 3: 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出:[8,9,9,9,0,0,0,1]
在逆序的列表中,每一项直接相加就是该位的值,通过设置一个变量记录进位。对于长度短的数字进行补0,然后相加,将处理后的每一项插入结果链表。 1、创建结果链表 2、遍历给定的两个链表 3、取结点值进行相加,并记录进位值carry,注意短数补0 4、遍历结束后,判断进位是否大于0,是则插入结果列表 在实现该题过程中,借鉴了官方的题解,最终按着自己的理解写出该题。
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *L=NULL, *node; //新建结果链表
int carry = 0; //存放进位
while(l1||l2) //链表非空继续计算
{
int a = l1 ?l1->val:0; //l1的结点非空则取该结点的值否则将该位置0
int b = l2 ?l2->val:0;
int sum = a + b +carry; //求和
if(!L) //如果结果列表为空,则使头指针指向结点node
{
node = malloc(sizeof(struct ListNode));
node->val = sum % 10;
node->next = NULL;
L = node;
}
else //在结果链表后插入结点
{
node->next = malloc(sizeof(struct ListNode));
node = node->next;
node->val = sum % 10;
node->next = NULL;
}
carry = sum / 10; //求进位
if(l1) //l1、l2非空后移
{
l1 = l1->next;
}
if(l2)
{
l2 = l2->next;
}
}
if(carry > 0) //将最后的进位插入链表
{
node->next = malloc(sizeof(struct ListNode));
node = node->next;
node->val = carry;
node->next = NULL;
}
return L;
}
在第一次实现中,在进行链表插入时出现错误,导致只能输出第一个数字和最后一个数字。原因则是反复将后续结点插入结果链表的第二个节点位置。导致无法得出正确结果,提交错误。