leetcode:使用链表添加两个数字

Question

我正试图解决一个涉及链表的中等级别问题，该问题类似于

给出了两个非空链表，表示两个非负整数。数字以相反的顺序存储，并且它们的每个节点都包含一个数字。将这两个数字相加，以链表形式返回总和。

您可以假设这两个数字不包含任何前导零，除了数字0本身。

python代码：

# 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
"""
l1_number = 0
i = 0
while l1:
l1_number+=l1.val*(10**i)
l1 = l1.next
i+=1

l2_number = 0
j = 0

while l2:
l2_number+=l2.val*(10**j)
l2 = l2.next
j+=1

sum_of_numbers = l2_number+l1_number

new_node=ListNode()
while sum_of_numbers > 0:
number = sum_of_numbers%10
while new_node.next:
new_node = new_node.next
new_node.next = ListNode(number)
sum_of_numbers=sum_of_numbers//10
return new_node

我收到了提交错误，因为预期的输出与生成的输出不同

Wrong Answer
Your input
[2,4,3]
[5,6,4]
Output
[0,8]
Expected
[7,0,8]

我假设由于某种原因，第一个元素被跳过了。如果能对这个问题做出解释，我将不胜感激。

Answer 1

它只是两个数字之间的简单求和。我们唯一应该添加一个虚拟节点作为起点：

class Solution:
def add(self,l1:ListNode,l2:ListNode)->ListNode:
# it is a starter node
dummy = ListNode()
cur = dummy
carry = 0
# l1 or l2 is each digit
# since it is reversed, we start to sum the 1's place. that makes it easier
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
val = v1 + v2 + carry
# because we are adding digits, if it is 15 carry will be 1                     
carry = val // 10
val = val % 10
cur.next = ListNode(val)
# update pointers
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next

Answer 2

我在ListNode类中添加了两个方法来帮助调试和测试(但解决方案类不需要(：

def __str__(self) -> str:  # for readability only
# could be made recursive
values = []
current = self
while True:
values.append(current.val)
if current.next is None:
break
else:
current = current.next
return repr(values)
def __eq__(self, other: object) -> bool:  # for testing
if isinstance(other, ListNode):
return (self.val == other.val) and (self.next == other.next)
else:
raise NotImplementedError

此外，我还创建了一个方便的函数来从整数创建ListNodes：

def make_into_a_list(n: int) -> ListNode:
assert n >= 0
if n < 10:
return ListNode(n)
else:
last_digit = n % 10
trunk = (n - last_digit) // 10  # integer division
return ListNode(val=last_digit, next=make_into_a_list(trunk))
assert str(make_into_a_list(0)) == "[0]"
assert str(make_into_a_list(4)) == "[4]"
assert str(make_into_a_list(10)) == "[0, 1]"
assert str(make_into_a_list(12)) == "[2, 1]"
assert str(make_into_a_list(100)) == "[0, 0, 1]"
assert str(make_into_a_list(123)) == "[3, 2, 1]"

这是我的解决方案：

class Solution(object):
def addTwoNumbers(self, l1, l2):
carry = 0
result_digits = []
while True:
if (l1 is not None) and (l2 is not None):
digits_sum = l1.val + l2.val + carry
if digits_sum >= 10:
carry = 1
digits_sum -= 10
result_digits.append(digits_sum)
l1 = l1.next
l2 = l2.next
elif (l1 is None) and (l2 is not None):
result_digits.append(l2.val + carry)
carry = 0
l2 = l2.next
elif (l1 is not None) and (l2 is None):
result_digits.append(l1.val + carry)
carry = 0
l1 = l1.next
else:  # both are None
break
result = None
for digit in reversed(result_digits):
result = ListNode(val=digit, next=result)
return result
num1 = ListNode(2, ListNode(4, ListNode(3)))
num2 = ListNode(5, ListNode(6, ListNode(4)))
assert Solution().addTwoNumbers(num1, num2) == make_into_a_list(807)

我还有一个递归解决方案：

class Solution(object):
def addTwoNumbers(self, l1, l2):
if not hasattr(self, "carry"):
# used to store the carry information through the recursive calls,
# without changing the method signature nor the __init__ code
self.carry = 0
if (l1 is not None) and (l2 is not None):
digits_sum = l1.val + l2.val + self.carry
if digits_sum >= 10:
self.carry = 1
digits_sum -= 10
return ListNode(val=digits_sum, next=self.addTwoNumbers(l1.next, l2.next))
elif (l1 is None) and (l2 is not None):
val = l2.val + self.carry
self.carry = 0
return ListNode(val=val, next=self.addTwoNumbers(l1, l2.next))
elif (l1 is not None) and (l2 is None):
val = l1.val + self.carry
self.carry = 0
return ListNode(val=val, next=self.addTwoNumbers(l1.next, l2))
else:
return None

Answer 3

天哪，需要两天时间才能解决！我的大脑融化了伙计们摘要：

class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
sum_list = [1, 2, 3, 4]
sum_list_reversed = sum_list[::-1]
# Magic happens ->
linked_list = ListNode()
linked_list_last_node = linked_list
for i, j in enumerate(sum_list_reversed):
if i == 0:
linked_list_last_node.val = j
else:
linked_list_last_node.next = ListNode(val=j)
linked_list_last_node = linked_list_last_node.next
# reading linkedlist
for i in range(len(sum_list_reversed)):
print(vars(linked_list))
linked_list = linked_list.next
# {'val': 4, 'next': <__main__.ListNode object at 0x000001837B7FFB70>}
# {'val': 3, 'next': <__main__.ListNode object at 0x000001837B812F98>}
# {'val': 2, 'next': <__main__.ListNode object at 0x000001837B812FD0>}
# {'val': 1, 'next': None}