两个数相加问题（链表）- Python - Leetcode - AttributeError

Question

我正在尝试解决这个问题 - 将 Leetcode

上的两个数字相加

我试过把两个链表都转成数组，然后做相加操作。现在，我正在努力将它们转换回链表，这是问题所需的输出。

任何人都可以检查我哪里出错了吗？我也收到属性错误：

AttributeError: 'NoneType' object has no attribute 'val'

这是我写的代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
  def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    a = l1 #pointers
    b = l2 #pointers
    arr1 = []
    arr2 = []

    while a.next is not None:
      arr1.append(a.val)
      a = a.next
    arr1.append(a.val) #storing the values of linked lists in arrays/lists

    while b.next is not None:
      arr2.append(b.val)
      b = b.next
    arr2.append(b.val) #storing the values of linked lists in arrays/lists

    rev1 = reversed(arr1) #reversed list
    rev2 = reversed(arr2) #reversed list

    inta = "".join(str(rev1)) #converting list to strings
    intb = "".join(str(rev2))

    c = str(inta + intb) #performing addition - the answer we wanted
    revc = reversed(c) #answer in string form - reversed (output in string at present)

    #trying to convert into linked list and return it
    q = l1
    for i in revc:
      q.val = i
      q = q.next
    return l1

Answer 1

NoneType 表示您正在使用 None 来处理 Class 或对象的实例。当上面的赋值或函数调用失败或 return 出现意外结果时，就会发生这种情况。

NoneType 是值 None 的类型。在这种情况下，变量生命周期的值为 None。通常发生的情况是调用缺少 return 的函数。

Answer 2

我在 Python3 做了这个，我建议你在 Python3 工作。

对于反向操作，您也可以使用就地 .reverse()，这样您就不必创建新变量。

另外，您的.join()操作有误。您需要遍历每个列表中的每个字符，而不是您正在做的是对列表进行字符串表示。

返回的链表的构造涉及为该列表的头部分配一个值，然后在遍历结果字符串时根据需要在新的 ListNodes 中添加数字。

我应该说，虽然我相信您的解决方案是新颖的，但我认为问题的本质是让您更轻松地使用链表。因此，我认为，围绕它们开展工作有点违背了该目标。

话虽如此，这是一种内存效率很高的解决方案，因为列表是 Python 中非常优化的数据结构。

祝你编码愉快！

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = l1 #pointers
        b = l2 #pointers
        arr1 = []
        arr2 = []

        while a:
          arr1.append(a.val)
          a = a.next

        while b:
          arr2.append(b.val)
          b = b.next

        arr1.reverse()
        arr2.reverse()

        inta = int("".join(str(x) for x in arr1)) #converting list to strings
        intb = int("".join(str(x) for x in arr2))

        c = list(str(inta + intb)) #performing addition - the answer we wanted

        # assign last digit to new ListNode which represents the head of returned LL
        head = l3 = ListNode(c.pop())

        c.reverse()

        # traverse remaining digits, assigning each to new ListNode
        for i in c:
            l3.next = ListNode(i)
            l3 = l3.next

        return head

Answer 3

您的错误是因为在您尝试访问 .val 时，a、b 或 q 是 None。

我不打算弄清楚为什么，相反我会解释你应该如何尝试解决这个问题。

如此指定问题的原因是您可以编写有效的解决方案。问题是提示您从基本单位（即单位、十、百、千等）编写长加法代码。

数字顺序相反，因此您可以从单位开始，携带任何超过 10 的东西。

243
564
^
start here

2 + 5 = 7, carry 0

243
564
 ^

4 + 6 = 0, carry 1

243
564
  ^

3 + 4 (+ 1) = 8, carry 0

therefore the answer is 

7 -> 0 -> 8

这样想意味着您可以编写更有效的响应。此方法的复杂度为 O(max(len(a), len(b)))，而您的方法的复杂度约为 O(8*max(len(a), len(b)))。差别不大，但计算量大，理解起来也不是很简单。

我确定可以在此处进行合理的改进，但这是我认为您应该瞄准的解决方案：

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry = 0
        original = value = ListNode(None)
        while True:
            if l1 is None and l2 is None:
                value.val = carry
                break
            elif l1 is None:
                value.val = l2.val + carry
                carry = 0
                l2 = l2.next
            elif l2 is None:
                value.val = l1.val + carry
                carry = 0
                l1 = l1.next
            else:
                car, val = divmod(l1.val + l2.val, 10)
                value.val = val + carry
                carry = car
                l1, l2 = l1.next, l2.next
            value.next = ListNode(None)
            value = value.next
        return original

编辑： 经过进一步思考，我意识到您也可以通过递归很好地完成它。

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def recursive_wrapper(l1, l2, carry):
            if l1 is None and l2 is None:
                return None
            elif l1 is None:
                res = ListNode(l2.val + carry)
                res.next = add_two_recursive(None, l2.next, 0)
            elif l2 is None:
                res = ListNode(l1.val + carry)
                res.next = add_two_recursive(l1.next, None, 0)
            else:
                car, val = divmod(l1.val + l2.val, 10)
                res = ListNode(val + carry)
                res.next = add_two_recursive(l1.next, l2.next, car)
            return res
        return recursive_wrapper(l1, l2, 0)

您可以边做边创建 ListNode。在每一点，它都是 l1 的头部加上 l2 的头部加上携带的数字作为值。然后获取 l1 和 l2 的下一个并重复。如果在任何时候 l1 或 l2 缺失，则将该值计为 0。一旦没有更多的数字，return None 表示结果结束。

Answer 4

class Solution:

    
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
    carry = 0
    head = curr = ListNode()
        
    while l1 and l2:
        total = l1.val + l2.val + carry
        curr.next = ListNode(total% 10)
        carry = total // 10
        l1,l2,curr = l1.next, l2.next,curr.next
            
    while l1:
        total = l1.val + carry
        curr.next = ListNode(total%10)
        carry = total // 10
        l1, curr = l1.next, curr.next
            
    while l2:
        total = l2.val + carry
        curr.next = ListNode(total%10)
        carry = total//10
        l2, curr = l2.next, curr.next
    if carry > 0:
        curr.next  = ListNode(carry)
                
    return head.next

两个数相加问题（链表）- Python - Leetcode - AttributeError

Add two numbers problem (linked list) - Python - Leetcode - AttributeError

linked-list

list

attributeerror

data-structures

python-3.x