LeetCode2 Add Two Numbers

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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.

样例

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

思路

给两个数位链表,输出求和之后的链表。
类似于高精度加法的过程,边求和边进位。为了处理起来方便,可以把小数加到大数上(无需得到真实大小,仅根据链表长度判断大小即可),然后由大数统一处理进位即可。
(唉,太久没写链表了,思路不清晰的话调试起来好痛苦…)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
* 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) {
int len1 = 0; // l1的长度
int len2 = 0; // l2的长度
ListNode* ptrL1 = l1; // 指向l1
ListNode* ptrL2 = l2; // 指向l2
while (ptrL1) { // 得到l1的长度
len1++;
ptrL1 = ptrL1->next;
}
while (ptrL2) { // 得到l2的长度
len2++;
ptrL2 = ptrL2->next;
}
if (len1 < len2) swap(l1, l2); // 将“大数”放在l1上
ptrL1 = l1; ptrL2 = l2;
while (ptrL2) { // 由于l2指向“小数”,故仅需判断l2是否为空即可
ptrL1->val += ptrL2->val; // l2 加到 l1 上
if (ptrL1->val >= 10) { // 处理进位
if (ptrL1->next == NULL) ptrL1->next = new ListNode(0);
ptrL1->next->val += (ptrL1->val) / 10;
ptrL1->val %= 10;
}
// 指向后继
ptrL1 = ptrL1->next;
ptrL2 = ptrL2->next;
}
// 处理后续的进位
while (ptrL1 && ptrL1->val >= 10) {
if (ptrL1->next == NULL) ptrL1->next = new ListNode(0);
ptrL1->next->val += (ptrL1->val) / 10;
ptrL1->val %= 10;
ptrL1 = ptrL1->next;
}
return l1;
}
};
分享到 评论