首页 > 代码库 > Add Two Numbers | LeetCode OJ 解题报告
Add Two Numbers | LeetCode OJ 解题报告
题目网址：https://oj.leetcode.com/problems/add-two-numbers/
题目描述：
You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
题目解答：
class Solution: #@return a ListNode def addTwoNumbers(self, l1, l2): return self.calc(l1,l2,0) def calc(self,l1,l2,plus): p1 = l1 p2 = l2 if p1 and p2: val = p1.val + p2.val + plus if val >= 10: val -= 10 plus = 1 else: plus = 0 elif p1 or p2: if plus == 0 : return p1 if p1 else p2 else : val = 1 + p1.val if p1 else 1 + p2.val if val >= 10: val -= 10 plus = 1 else: plus = 0 elif not p1 and not p2: if plus == 0 : return None else : return ListNode(1) else: print "sb" l = ListNode(val) l.next = self.calc(p1.next if p1 else None,p2.next if p2 else None,plus) return l
总的思路是设计一个递归算法，这个算法的工作就是利用传递进来的两个链表节点信息分类进行处理，完成之后调用自身，传入不同的参数，从而得到下一个节点，然后使得本节点连接下一个节点。分类的思路是：如果两个节点都不是None，那么就进行最自然的操作；如果一个是None，上一次运算无进位，那么直接返回不是None的那么节点，如果有进位，按照正常情况处理（只不过只是一个节点的数值与进位相加）；如果两个都是None，上一次运算无进位，那么返回None，有进位，返回ListNode（1）。
下面是一个思路上更简单的做法，算是上面那段代码的简化版吧
def calc(self,l1,l2,plus): p1 = l1 p2 = l2 val = 0 if p1 or p2: if p1: val += p1.val if p2: val += p2.val val += plus plus = val/10 val %= 10 l = ListNode(val) l.next = self.calc(p1.next if p1 else None,p2.next if p2 else None,plus) return l elif plus: return ListNode(1) else: return None
有递归的方法，就有不是递归的方法：
def addTwoNumbers(self, l1, l2): return self.calc(l1,l2) def calc(self,l1,l2): plus = 0 head = ListNode(0) p = head if not l1: return l2 if not l2 : return l1 while l1 or l2 or plus: sum = 0 if l1: sum += l1.val if l2: sum += l2.val sum += plus val = sum % 10 plus = sum / 10 p.next = ListNode(val) p = p.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return head.next
以上
Add Two Numbers | LeetCode OJ 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。