1 """
2 You are given two non-empty linked lists representing two non-negative integers. 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.
3 You may assume the two numbers do not contain any leading zero, except the number 0 itself.
4 Example:
5 Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
6 Output: 7 -> 0 -> 8
7 Explanation: 342 + 465 = 807.
8 """
9
10 """
11 对于双链表合并的问题，一般方法
12 先建立一个头结点，最后用来返回结果first.next
13 再将头结点复制出一个指针p = first，用来向后增加链表结点
14 对两个链表先同时遍历 while l1 and l2: p=p.next
15 然后再分别单独遍历剩余的 while l1: while l2:
16 """
17 class ListNode:
18 def __init__(self, x):
19 self.val = x
20 self.next = None
21
22 class Solution1:
23 def addTwoNumbers(self, l1, l2):
24 head = ListNode(0)
25 first = head
26 temp = 0
27 while l1 and l2:
28 if l1.val + l2.val + temp < 10:
29 head.next = ListNode(l1.val+l2.val+temp)
30 temp = 0
31 else:
32 head.next = ListNode((l1.val+l2.val+temp)%10)
33 temp = 1
34 l1 = l1.next
35 l2 = l2.next
36 head = head.next
37 while l1:
38 if l1.val + temp < 10:
39 head.next = ListNode(l1.val+temp)
40 temp = 0
41 else:
42 head.next = ListNode((l1.val+temp)%10)
43 temp = 1
44 l1 = l1.next
45 head = head.next
46 while l2:
47 if l2.val + temp < 10:
48 head.next = ListNode(l2.val+temp)
49 temp = 0
50 else:
51 head.next = ListNode((l2.val+temp)%10)
52 temp = 1
53 l2 = l2.next
54 head = head.next
55 #案例没有通过，加上了下面两行
56 #Input: [5]
57 # [5]
58 #Output: [0]
59 #Expected: [0,1]
60 if temp > 0:
61 head.next = ListNode(1)
62 return first.next
63
64 """
65 解法二：将三个while循环合并为一个
66 """
67 class ListNode:
68 def __init__(self, x):
69 self.val = x
70 self.next = None
71
72 class Solution2:
73 def addTwoNumbers(self, l1, l2):
74 first = ListNode(0)
75 p = first
76 carry = 0
77 while l1 or l2:
78 x = l1.val if l1 else 0 #!!!合并while循环的关键的点
79 y = l2.val if l2 else 0
80 res = x + y + carry
81 carry = res // 10
82 p.next = ListNode(res%10)
83 l1 = l1.next if l1 else 0 #!!!合并while循环的关键的点
84 l2 = l2.next if l2 else 0
85 p = p.next
86 if carry > 0: #很容易忽略的情况,最后还有进位
87 p.next = ListNode(1)
88 return first.next
