python算法日记（链表系列）_leetcode 2. 两数相加小菜狗的算法日记(链表)

【python算法日记（链表系列）_leetcode 2. 两数相加】给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
用迭代的方法：

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: res = l3 = ListNode(0) flag = 0# flag表示是否进位 while l1 or l2: sums = 0 if l1:#有就加，没有就不加，用来处理长短不一 sums = l1.val l1 = l1.next if l2: sums += l2.val l2 = l2.next sums += flag if sums<=9: l3.next = ListNode(sums) l3 = l3.next flag = 0 else: flag = sums//10 l3.next = ListNode(sums%10) l3 = l3.next if flag: l3.next = ListNode(1) #l1,l2都没有了还有进位的情况 return res.next

迭代二：

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: flag = 0 cur = l3 = ListNode(0) while l1 and l2:# 处理l1,l2同时在的情况，如果有一个有，有一个没有就补零 sums = l1.val + l2.val + flag if sums//10==0: l3.next=ListNode(sums) flag = 0 else: l3.next=ListNode(sums%10) flag = 1 l3 = l3.next if l1.next and l2.next: l1 = l1.next l2 = l2.next elif l1.next and not l2.next: l2.next = ListNode(0) l1 = l1.next l2 = l2.next elif l2.next and not l1.next: l1.next = ListNode(0) l1 = l1.next l2 = l2.next else: break if flag: l3.next = ListNode(1) return cur.next

迭代二精简了一下：

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: flag = 0 cur = l3 = ListNode(0) while l1 and l2: sums = l1.val + l2.val + flag if sums//10==0: l3.next=ListNode(sums) flag = 0 else: l3.next=ListNode(sums%10) flag = 1 l3 = l3.next if not l1.next and not l2.next: break l1 = l1.next or ListNode(0) l2 = l2.next or ListNode(0) if flag: l3.next = ListNode(1) return cur.next

递归：不用额外的链表，直接把l1改掉：
递归终止条件：两个链表都没有值了。递归重复在做的事：相加，判断是否进位。递归返回值：节点。
这里先处理相加等操作，再进入递归。相当于二叉树先序，先存根节点值，再进递归。

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: def loop(l1,l2,flag): if not l1 and not l2: #递归终止条件 return ListNode(1) if flag else None #走完还有进位，返回节点1，没有返回None l1 = l1 or ListNode(0) #有一个有有一个没有补零 l2 = l2 or ListNode(0) sums = l1.val+l2.val+flag if sums<=9: l1.val=sums#直接改l1装结果 flag = 0 else: l1.val = sums%10 flag = 1 l1.next = loop(l1.next,l2.next,flag) return l1 return loop(l1,l2,0)# # 新建一个节点去接也行 # def loop(l1,l2,flag): #if not l1 and not l2: #return ListNode(1) if flag else None #l1 = l1 or ListNode(0) #l2 = l2 or ListNode(0) #sums = l1.val+l2.val+flag #l3 = ListNode(0) #l3.val = sums%10 #flag = sums//10 #l3.next = loop(l1.next,l2.next,flag) #return l3 # return loop(l1,l2,0)

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
21行 7.next21行 0.next21行8.next11行返回None接到8后面22行返回8->None
21行 0->8->None 22行返回21行7->0->8->None 22行返回