作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/add-two-numbers-ii/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.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
题目大意
有两个链表，分别是正序的十进制数字。现在要求两个十位数字的和，要求返回的结果也是链表。
解题方法
先求和再构成列表
选择easy模式的话，可以直接先求出和，再构建链表。
这么做的前提是python中没有最大的整数，所以无论怎么着不会越界！
Python代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
num1 = ''
num2 = ''
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
add = str(int(num1) + int(num2))
head = ListNode(add[0])
answer = head
for i in range(1, len(add)):
node = ListNode(add[i])
head.next = node
head = head.next
return answer
使用栈保存节点数字
可以采用翻转后变成 Add Two Numbers 的题目，但是题目说了最好别那么做。那么可以使用一个栈来完成类似的操作。上一个题目的结果也是数字的倒序的，而这个题要求结果是正序，那么加的过程中采用头插法，一直向头部插入新的节点就好了。
步骤非常类似Add Two Numbers。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
stack1 = []
stack2 = []
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
answer = None
carry = 0
while stack1 and stack2:
add = stack1.pop() + stack2.pop() + carry
carry = 1 if add >= 10 else 0
temp = answer
answer = ListNode(add % 10)
answer.next = temp
l = stack1 if stack1 else stack2
while l:
add = l.pop() + carry
carry = 1 if add >= 10 else 0
temp = answer
answer = ListNode(add % 10)
answer.next = temp
if carry:
temp = answer
answer = ListNode(1)
answer.next = temp
return answer
二刷的时候使用的C++的vector来存储的每个节点的值，然后再做的加法。每次构建新节点使用的头插法，所以结果同样是题目要求的倒序。
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) {
vector<int> v1, v2;
while (l1) {
v1.push_back(l1->val);
l1 = l1->next;
}
while (l2) {
v2.push_back(l2->val);
l2 = l2->next;
}
const int M = v1.size(), N = v2.size();
int i1 = M - 1, i2 = N - 1;
int carry = 0;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (i1 >= 0 || i2 >= 0 || carry) {
int add = (i1 >= 0 ? v1[i1] : 0) + (i2 >= 0 ? v2[i2] : 0) + carry;
carry = add >= 10 ? 1 : 0;
add %= 10;
ListNode* cur = new ListNode(add);
cur->next = dummy->next;
dummy->next = cur;
if (i1 >= 0)
--i1;
if (i2 >= 0)
--i2;
}
return dummy->next;
}
};
类似题目
2. Add Two Numbers
989. Add to Array-Form of Integer
日期
2018 年 2 月 26 日
2019 年 2 月 22 日 —— 这周结束了