首页 > > 程序设计 > C/C++ >

Add Two Numbers

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

题目：

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 };