Add Two Numbers

2018-06-17 23:17:16来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input:     (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:    7 -> 0 -> 8

思路:

1.这道题用链表的形式实现,分别对两个链表进行遍历,相应项相加。

2.遵循多位数加法原则,满十进一。故需要对两数相加所得的数值进行判断是否大于十。这里采取便捷的做法是取所得值除十的余数,而判断是否有进位则看其除以十所得商为何值。

3.注意链表上数值的顺序,可以从头开始遍历,将计算结果插入新建节点的尾部。

4.由于给出的两个链表可能存在长短不一的情况。因此要注意将较长的链表单独处理。

代码:

以下是我的代码,AC,106ms

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         ListNode* answer = new ListNode(0);
13         ListNode *curr = answer;
14         // 计数值,用于计算两数之和
15         int incs = 0;
16         while (l1 != NULL && l2 != NULL){
17             incs = l1->val + l2->val + incs;
18             // 只取和数的个位
19             curr->next = new ListNode(incs%10);
20             l1 = l1->next;
21             l2 = l2->next;
22             curr = curr->next;
23             // 若满十则进一,留在下一个节点计算时加上
24             incs = incs / 10;
25         }
26         // 考虑到链表长度不一的情况,需要分别考虑
27         while (l1 != NULL){
28             incs = l1->val + incs;
29             curr->next = new ListNode(incs%10);
30             l1 = l1->next;
31             curr = curr->next;
32             incs = incs / 10; 
33         }
34         while (l2 != NULL){
35             incs = l2->val + incs;
36             curr->next = new ListNode(incs%10);
37             l2 = l2->next;
38             curr = curr->next;
39             incs = incs / 10; 
40         }
41         // 若链表最后一位数值相加大于十,则需在结果中新增一个节点来记录
42         if (incs == 1)
43             curr->next = new ListNode(1);
44         // 一开始建立链表时头节点赋值为0,故返回时从下一位开始
45         return answer->next;
46     }
47 };

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:bzoj3809 -- 莫队+分块

下一篇:读书笔记 effective c++ Item 18 使接口容易被正确使用,不容易