LeetCode|【LeetCode】445. Add Two Numbers II 解题报告（Python & C++） LeetCode|算法

作者：负雪明烛
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 = Noneclass 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 = Noneclass 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 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
日期 【LeetCode|【LeetCode】445. Add Two Numbers II 解题报告（Python & C++）】2018 年 2 月 26 日
2019 年 2 月 22 日 —— 这周结束了