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

Question

I am trying to solve this problem - Add two numbers which is on Leetcode

I tried to convert both the linked lists into arrays and then performed the add operation. Now, I am struggling to convert them back to the linked list which is the desired output for the problem.

Can anyone check where I am going wrong? I am also getting an Attribute error:

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

This is the code I wrote:

# 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

ppwater · Accepted Answer · 2020-11-18 14:04:30Z

2

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

edited Nov 18, 2020 at 14:04

ppwater

2,2774 gold badges17 silver badges30 bronze badges

answered Nov 18, 2020 at 11:01

Muthoni

213 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Muthoni Over a year ago

leetcode.com/problems/add-two-numbers/discuss/771545/… . Found this to be way easier

mechanical_meat · Accepted Answer · 2019-12-25 21:52:24Z

I did this in Python3, and I recommend you work in Python3.

For the reversing operations, you can alternatively use .reverse() which is in-place so you don't have to create new variables.

Also, your .join() operation was incorrect. You need to iterate over each character in each list instead of what you were doing which is to make a string representation of the list.

The construction of the returned linked list involves assigning a value to the head of that list, then as needed adding digits in new ListNodes as you traverse your result string.

I should say that while I believe yours to be a novel solution, I think that the spirit of the problem is to get you more comfortable working with linked lists. So working around them is, I believe, slightly against that goal.

Having said that, this is a highly memory-efficient solution as lists are very optimised data structures in Python.

Happy coding to you!

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

Sai prateek · Accepted Answer · 2019-12-25 21:05:02Z

1

NoneType means that you are working with None where you suppose to work the instance of Class or Object. This occurs when an assignment or function call up above failed or returned an unexpected result.

The NoneType is the type of the value None. In this case, the variable lifetime has a value of None.Usually happen is to call a function missing a return.

answered Dec 25, 2019 at 21:05

Sai prateek

11.9k10 gold badges56 silver badges67 bronze badges

Comments

blueteeth · Accepted Answer · 2019-12-25 22:16:04Z

Your error is because at some point a, b, or q is None when you try to access .val.

I'm not going to figure out why, instead I'll explain how you should be trying to solve this problem.

The reason the problem is specified like that is so you can write an efficient solution. The question is prompting you to code long addition from base units - i.e units, tens, hundreds, thousands, etc.

The numbers are in reverse order so you can start with the units and carry anything that goes over 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

Thinking about it like this means you can code a much more efficient response. Complexity for this is O(max(len(a), len(b))), whereas for your method it is around O(8*max(len(a), len(b))). Not a massive difference, but there's a lot of wasted calculation, and it isn't simple to understand.

I'm sure there are logical improvements that can be made here, but this is the sort of solution I think you should be aiming for:

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

Edit: With further thought I've realised you can also do it really nicely with recursion.

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)

You create the ListNode as you go. At each point it's the head of the l1 plus the head of l2 plus the carrying number as the value. Then get the next for l1 and l2 and repeat. If at any time the l1 or l2 is missing, count the value as 0. Once there are no more numbers, return None signifying the end of the result.

Collectives™ on Stack Overflow

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

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related