典型网站开发的一般流程,大连微信网站制作,郑州网页制作案例,网页排版怎么设置目录 题目题目描述示例 1#xff1a;示例 2#xff1a;示例 3#xff1a;提示#xff1a;原题链接 题解解题思路代码实现#xff08;C#xff09; 题目
题目描述
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xf… 目录 题目题目描述示例 1示例 2示例 3提示原题链接 题解解题思路代码实现C 题目
题目描述
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。 请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。
示例 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]
提示
每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零
原题链接
LeetCode 2. 两数相加
题解
解题思路
每个链表中的节点数在范围 [1, 100] 内超出int或long的表示范围故不能将链表转为数字相加。采取逐位相加计算进位的方式 声明一个链表用来存放相加后的结果。不断地取两个链表的最低位相加后加上进位初值为0判断是否需要进位需要进位则更新进位信息。进位判断完成后用尾插法将该数字插入到链表中头插法逆转元素顺序尾插法顺序不变。某一个链表遍历完后需要对另一个链表单独遍历进行同样的操作。两个链表都遍历完后需要检验最后是否有进位有进位则用尾插法将进位插入到链表中。 算法笔记p253链表处理。
代码实现C
typedef struct ListNode node; // 表示声明的是一个结点
typedef struct ListNode List; // 表示声明的是一个单链表// 单链表向指定结点后插入结点
node *insert(node *pre, int value) {node *p (node *) malloc(sizeof(node));p-val value;node *r pre-next;pre-next p;p-next r;return p;
}List *head NULL; // 新建一个链表
node *tail NULL; // 尾指针
int carry 0; // 进位// 计算进位和插入结点
void calculate(int sum) {carry 0; // 进位已经加到sum中,置为0if (sum 10) { // 如果可以产生进位carry sum / 10; // 更新进位sum % 10; // 取个位}tail insert(tail, sum); // 尾插法插入结点
}struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {head (List *) malloc(sizeof(List)); // 初始化链表head-next NULL;tail head; // 尾指针一开始指向头结点carry 0; // 初始化进位for (; l1 l2; l1 l1-next, l2 l2-next) // 计算l1和l2共同长度部分calculate(l1-val l2-val carry);for (; l1; l1 l1-next) // 计算l1剩余部分calculate(l1-val carry);for (; l2; l2 l2-next) // 计算l2剩余部分calculate(l2-val carry);if (carry ! 0) // 如果处理完l1和l2所以位数,还有进位tail insert(tail, carry); // 尾插法插入进位return head-next;
}
