Halo

A magic place for coding

0%

LeetCode解题报告(一)-- 445. Add Two Numbers II

Problem

Description: You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

Example:

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

Analysis

  从题目看是一个关于链表的加法运算,其涉及两个知识点:链表以及大数加法,难点在于题目给出的输入是从高位到低位的,而加法则需要从低位到高位

Solution

  为了解决链表的高位问题(不考虑把链表reverse的方法,效率太低),这里可以巧妙地借助stack来实现。分别将两个链表的数字压入两个栈中。再从栈顶逐个取出相加即可。

Tips:

  • 逐位相加时,需要考虑上一位的进位。
  • 最后返回链表head指针时,需要判断最高位是否为0,若为0,则返回head-next;否则,直接返回head.

Code

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
47
48
49
50
/**
* 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) {
stack<int> s1;
stack<int> s2;

while (l1 != NULL) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2 != NULL) {
s2.push(l2->val);
l2 = l2->next;
}

int add = 0;
ListNode* result = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
int sum = result->val;
add = 0; // reset
if (!s1.empty()) {
sum += s1.top();
s1.pop();
}
if (!s2.empty()){
sum += s2.top();
s2.pop();
}

if (sum >= 10) {
sum %= 10;
add = 1;
}

result->val = sum;
ListNode* newNode = new ListNode(add);
newNode->next = result;
result = newNode;
}
return result->val == 0 ? result->next : result;
}
};

Summary

  开始的时候,我的思路是分别计算出两条链所代表的数,然后相加后再逐个数字提取出来插入链表,这种做法的问题在于无法处理数值较大的数。因此就把思路转向了逐位求和的方式。在数据结构中,stack是一个可以用于reverse数据的工具,因此我使用了stack来在链表中获取最低位数字,随后的求和就比较简单了。本题的分析就到这里,谢谢!

Welcome to my other publishing channels