leetcode2 Add Two Numbers

 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