使用python完成LeetCode问题#2

Question

下面是我的代码，它试图将两个数字相加，这两个数字也以相反的顺序存储在链表中，并返回和作为链表。

但是当我尝试在LeetCode中运行这段代码时，它指出这超出了时间。我想它可能会卡在while循环中?

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
result = ListNode()
carry = 0 

while l1 != None or l2 != None or carry:
if l1 == None:
v1 = 0
else:
v1 = l1.val

if l2 == None:
v2 = 0
else:
v2 = l2.val

total = v1 + v2 + carry 
carry = total // 10
total = total % 10

result.next = ListNode(total)

if l1 != None:
l1.next

if l2 != None:
l2.next

return result

Answer 1

我在您写的代码中只做了几处修改。

result = ListNode(0)
result_tail = result #### added 
carry = 0 

while l1 or l2 or carry:
if l1 == None:
v1 = 0
else:
v1 = l1.val

if l2 == None:
v2 = 0
else:
v2 = l2.val

total = v1 + v2 + carry 
carry = total // 10
total = total % 10

result_tail.next = ListNode(total)  ### edited
result_tail = result_tail.next   ### added

if l1 != None:
l1 = l1.next ### edited
else:
l1 = None   ### added

if l2 != None:
l2 = l2.next    ### edited
else:
l2 = None    ### added

return result.next   ### edited

我希望你知道的主要事情是，当你写l1.next时，你只是给出一个需要一个变量来存储值的命令，因此改变了l1 = l1.next。类似地，当您编写相同的语句时，您需要一个计数器else语句，当if条件失败时，您需要处理该条件。由于该条件不存在，while循环无限运行。

最后一部分是我添加了一个result_tail。通过尝试和错误，我看到，如果我们不添加它，那么结果的值得到更新，而不是被追加。

最后，这不是一个愚蠢的问题。这只是一个友好的建议，如果你是新手，不要从所有概念的简单代码开始编写中级代码。它将帮助你更多地了解python中的特定交易，如字典、默认字典、列表推导、列表遍历、元组、集合、枚举器等。你可能以前做过竞争性编码，但说实话，新的一局总是从0开始。

Answer 2

分析

这只是一个简单的初等加法问题。唯一的区别是要添加的数字由链表表示，其中每个数字由该链表的节点表示。

如果我们看这个例子，我们会看到数字的顺序是相反的，即

First node => ones place
Second node => tens place
Third node => hundreds place
... and so on.

则2 ->4→3会使342年和5→6→4实际上等于465。

我们将返回一个新的链表，其节点将表示给定的两个链表所表示的数字之和的数字。

方法

1. 遍历两个链表
2. 在每次迭代中，在链表节点中添加数字。
3. 如果列表不相等，则较小的列表将在较长的列表之前结束。在本例中，我们将只放置
4. 如果两位数字的和大于9，那么我们必须找出要在下一次迭代中添加的进位。

这只不过是一个简单的加法。这里唯一的挑战可能是避免NullPointerException，这在基于链表的问题中非常常见。

时间复杂度。由于两个链表只迭代一次，所以时间复杂度为O(m + n)。这里m和n是两个链表的节点数。

空间复杂性由于我们使用额外的空间只对我们的变量,我们的空间复杂度是O(1)。有人可能会争辩说，我们使用另一个列表来存储我们的结果，所以空间复杂度也应该是O(m + n)。但这是我们不使用我们的算法的列表，我们使用它的结果在问题中被问到(我很想知道你对此的看法)。

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
# Head of the new linked list - this is the head of the resultant list
head = None
# Reference of head which is null at this point
temp = None
# Carry
carry = 0
# Loop for the two lists
while l1 is not None or l2 is not None:
# At the start of each iteration, we should add carry from the last iteration
sum_value = carry
# Since the lengths of the lists may be unequal, we are checking if the
# current node is null for one of the lists
if l1 is not None:
sum_value += l1.val
l1 = l1.next
if l2 is not None:
sum_value += l2.val
l2 = l2.next
# At this point, we will add the total sum_value % 10 to the new node
# in the resultant list
node = ListNode(sum_value % 10)
# Carry to be added in the next iteration
carry = sum_value // 10
# If this is the first node or head
if temp is None:
temp = head = node
# for any other node
else:
temp.next = node
temp = temp.next
# After the last iteration, we will check if there is carry left
# If it's left then we will create a new node and add it
if carry > 0:
temp.next = ListNode(carry)
return head