内容简介:本文首发于公众号「五分钟学算法」,是个人网站:www.cxyxiaowu.com题目来源于 LeetCode 上第 2 号问题:两数相加。题目难度为 Medium,目前通过率为 33.9% 。
本文首发于公众号「五分钟学算法」,是 图解 LeetCode 系列文章之一。
个人网站:www.cxyxiaowu.com
题目来源于 LeetCode 上第 2 号问题:两数相加。题目难度为 Medium,目前通过率为 33.9% 。
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807 复制代码
题目解析
设立一个表示进位的变量 carried
,建立一个新链表,把输入的两个链表从头往后同时处理,每两个相加,将结果加上 carried
后的值作为一个新节点到新链表后面。
动画描述
代码实现
/// 时间复杂度: O(n) /// 空间复杂度: O(n) /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *p1 = l1, *p2 = l2; ListNode *dummyHead = new ListNode(-1); ListNode* cur = dummyHead; int carried = 0; while(p1 || p2 ){ int a = p1 ? p1->val : 0; int b = p2 ? p2->val : 0; cur->next = new ListNode((a + b + carried) % 10); carried = (a + b + carried) / 10; cur = cur->next; p1 = p1 ? p1->next : NULL; p2 = p2 ? p2->next : NULL; } cur->next = carried ? new ListNode(1) : NULL; ListNode* ret = dummyHead->next; delete dummyHead; return ret; } }; 复制代码
以上所述就是小编给大家介绍的《LeetCode 第 2 号问题:两数相加》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Python语言及其应用
[美] Bill Lubanovic / 丁嘉瑞、梁杰、禹常隆 / 人民邮电出版社 / 2016-1 / 79.00元
本书介绍Python 语言的基础知识及其在各个领域的具体应用,基于最新版本3.x。书中首先介绍了Python 语言的一些必备基本知识,然后介绍了在商业、科研以及艺术领域使用Python 开发各种应用的实例。文字简洁明了,案例丰富实用,是一本难得的Python 入门手册。一起来看看 《Python语言及其应用》 这本书的介绍吧!