leetcode刷题第二天<两数相加>
2019-02-27 11:51:15来源:博客园 阅读 ()
题目描述
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
首先是c++
最开始采用官方题解java该c++版本的,代码如下
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummyHead = new ListNode(0); ListNode* p = l1; ListNode* q = l2; ListNode* curr = dummyHead; int carry = 0; while (p != 0 || q != 0) { int x = (p != 0) ? p->val : 0; int y = (q != 0) ? q->val : 0; int sum = carry + x + y; carry = sum / 10; curr->next = new ListNode(sum % 10); curr = curr->next; if (p != 0) p = p->next; if (q != 0) q = q->next; } if (carry > 0) { curr->next = new ListNode(carry); } return dummyHead->next; } };
思路为申请一个新的链表空间进行存储,然后分别进行链表的传递,接着判断链表的值与0的关系返回,最后求和,然后%10取余数,最后判断余数和和0的关系,然后返回即可
另外一种大佬解法
是申请两个链表的空间,然后如果链表不为空进行遍历相加,最后在判断链表和余数与9的关系,最后返回第二个链表空间。
代码如下
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* list_head= new ListNode(0); ListNode* list_node=list_head; while(1) { int sum=list_node->val; if(l1) { sum+=l1->val; l1=l1->next; } if(l2) { sum+=l2->val; l2=l2->next; } list_node->val=sum%10; if(l1||l2||sum>9) { list_node->next=new ListNode(sum/10); list_node=list_node->next; } else{ break; } } return list_head; } };
最后再用python走下
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: add_num = 0 new_list = ListNode(0) cur = new_list cur1 = l1 cur2 = l2 while cur1 or cur2: if cur1 and cur2: value = cur1.val + cur2.val + add_num elif cur1: value = cur1.val + add_num elif cur2: value = cur2.val + add_num cur.next = ListNode(value % 10) add_num = 0 if value > 9: add_num = 1 cur = cur.next if cur1: cur1 = cur1.next if cur2: cur2 = cur2.next if add_num: cur.next = ListNode(add_num) cur = cur.next return new_list.next
c实现算法如下
int remainder = 0; int integer = 0; int sum = 0; int l1_val = 0; int l2_val = 0; struct ListNode *l_end = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *l_head = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *l_node; struct ListNode *l1_p = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *l2_p = (struct ListNode *)malloc(sizeof(struct ListNode)); l1_p = l1; l2_p = l2; /*尾插法,当前只有头结点,且为空*/ l_head->next = NULL; l_end = l_head; while((l1_p != NULL) || (l2_p != NULL)) { l1_val = (l1_p != NULL)?l1_p->val:0; l2_val = (l2_p != NULL)?l2_p->val:0; sum = l1_val + l2_val + integer; remainder = sum %10; l_node = (struct ListNode *)malloc(sizeof(struct ListNode)); l_node->next = NULL; l_node->val = remainder; l_end->next = l_node; l_end = l_node; if(l1_p != NULL) { l1_p = l1_p->next; } if(l2_p != NULL) { l2_p = l2_p->next; } integer = sum /10; } if(integer > 0) { l_node = (struct ListNode *)malloc(sizeof(struct ListNode)); l_node->next = NULL; l_node->val = integer; l_end->next = l_node; l_end = l_node; } return l_head->next; }
原文链接:https://www.cnblogs.com/kk328/p/10440625.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- leetcode 反转链表 2020-06-06
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- [题记]字符串转换整数-leetcode 2020-04-03
- [题记]有效括号的嵌套深度-leetcode 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash