代码git：History for 2. 两数相加.py - WankkoRee/LeetCodeAnswersWithPython3
这题又是各种卡边缘条件的一题...
先是写个最基本的链表合并，然后简单地考虑一下进位。（assert False只是我当调试断点用的，因为这题结果是对象，不太好直接检查，所以就下断点手动检查了）
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while p and q:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
p = p.next
q = q.next
if ex:
if p:
p.val += ex
else: # q
q.val += ex
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
assert False结果自然是没过，数据是addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))，因为进位的问题没考虑完全，即使有一条链表已经处理完了，只剩下单条链表，进位也可能不止一次，比如说这个9999999+9999的情况，就需要在合并结束后连续进位，于是补一下结束后的连续进位，再看看正确率。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while p and q:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
p = p.next
q = q.next
if ex:
if p:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
break
else: # q
while q:
q.val += ex
if q.val >= 10:
ex = 1
q.val -= 10
else:
break
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False然后因为是没测直接交的，所以又在刚才的数据上翻车了，翻的原因是忘记写链表指针后移了...
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while p and q:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
p = p.next
q = q.next
if ex:
if p:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
break
p = p.next
else: # q
while q:
q.val += ex
if q.val >= 10:
ex = 1
q.val -= 10
else:
break
q = q.next
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False然后又风风火火地交，风风火火地裂开，主要还是太自信了，最后没有处理进位导致溢出了1个长度的问题，所以就补一下进位的溢出修复。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while p and q:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
p = p.next
q = q.next
if ex:
if p:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
break
p = p.next
if ex:
p.next = ListNode(ex)
else: # q
while q:
q.val += ex
if q.val >= 10:
ex = 1
q.val -= 10
else:
ex = 0
break
q = q.next
if ex:
q.next = ListNode(ex)
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False结果就报错了，因为在处理最后的溢出进位时，p或者q已经是None了，压根不是ListNode对象...于是就把这处的处理上移一下，确保还没后移指针时先判断一下要不要处理。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while p and q:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
p = p.next
q = q.next
if ex:
if p:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
if p.next:
p = p.next
else:
p.next = ListNode(ex)
break
else:
break
else: # q
while q:
q.val += ex
if q.val >= 10:
ex = 1
q.val -= 10
if q.next:
q = q.next
else:
q.next = ListNode(ex)
break
else:
break
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
assert False这个边缘数据总算过了，但是又来了个addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))的边缘数据，这个纯属是刚才考虑q比p长的时候想岔了，忘记把q尾部数据接到p上面去了，不过既然拼接了链表的话，那就下面进位不用管q的事了，所有数据全在p上了。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while True:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
if p.next:
p = p.next
else:
p.next = q.next
p = p.next
break
if q.next:
q = q.next
else:
break
if ex:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
if p.next:
p = p.next
else:
p.next = ListNode(ex)
break
else:
break
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
assert False然后又来个addTwoNumbers(ListNode(5), ListNode(5))的边缘数据，这个的话是因为刚才改动的时候，数据判定的位置不太合理造成的，导致把p给整成None了，所以把上面指针后移的判断给改改就行。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while True:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
if p.next:
p = p.next
if q.next:
q = q.next
else:
break
else:
if q.next:
p.next = q.next
p = p.next
break
else:
if ex: # 特殊情况
p.next = ListNode(ex)
ex = 0
break
if ex:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
if p.next:
p = p.next
else:
p.next = ListNode(ex)
break
else:
break
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
d = solution.addTwoNumbers(ListNode(5), ListNode(5))
assert False结果这回一改连第一个数据都没过了，仔细看了下跳出情况发现not p.next and not q.next and not ex的时候本来也得跳，结果整忘了，所以直接把not p.next and not q.next and ex的break给共享一下就完事。
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
p = l1
q = l2
ex = 0
while True:
p.val += q.val + ex
if p.val >= 10:
ex = 1
p.val -= 10
else:
ex = 0
if p.next:
p = p.next
if q.next:
q = q.next
else:
break
else:
if q.next:
p.next = q.next
p = p.next
break
else:
if ex: # 特殊情况
p.next = ListNode(ex)
ex = 0
break
if ex:
while p:
p.val += ex
if p.val >= 10:
ex = 1
p.val -= 10
if p.next:
p = p.next
else:
p.next = ListNode(ex)
break
else:
break
return l1
solution = Solution()
a = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(3))), ListNode(5, ListNode(6, ListNode(4))))
b = solution.addTwoNumbers(ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9, ListNode(9))))))), ListNode(9, ListNode(9, ListNode(9, ListNode(9)))))
c = solution.addTwoNumbers(ListNode(2, ListNode(4, ListNode(9))), ListNode(5, ListNode(6, ListNode(4, ListNode(9)))))
d = solution.addTwoNumbers(ListNode(5), ListNode(5))
assert False终于过了，这测试数据仔细得有点离谱。
执行用时：
40 ms, 在所有Python3提交中击败了99.45%的用户
内存消耗：15.1 MB, 在所有Python3提交中击败了22.40%的用户
通过测试用例：1568 / 1568