Why am I getting a NoneType error after reversing a linked list and processing the head of the new linked list?

Question

I am writing code to answer the following question: "for two linked lists l1 and l2 that contain positive integers (and have at least one node), return their sum as a linked list. "

For example:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

The way I am coding this is to reverse both linked lists, then add them (add this is how you would add two numbers)

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1==[0]:
            return l2 
        
        if l2==[0]:
            return l1
        
        #Reversing both linked lists l1 & l2
        prev = None
        pointer = l1

        while pointer:
            curr = pointer.next 
            pointer.next = prev
            prev = pointer
            pointer = curr

        prev2 = None
        pointer2 = l2

        while pointer2:
            curr2 = pointer2.next 
            pointer2.next = prev2
            prev2 = pointer2
            pointer2 = curr2

        #prev and prev2 are the heads of the reversed linked list(I've tested this) 


        #Creating a new linked list that is the addition of the two reversed linked list
        l3=ListNode(0)
        start_l3 = l3
        carry = 0 

        while prev or prev2:
            if prev.val + prev2.val >9:
                carry =1
            else:
                carry = 0
            s = prev.val + prev2.val + carry
            l3.next = ListNode(s)
            l3=l3.next
            prev=prev.next
            prev2=prev2.next

        if carry ==1:
            l3.next = ListNode(1)

        return start_l3.next

When I run this for the input given above, I get a "NoneType object has no attribute val for the line if prev.val + prev2.val >9:

Any ideas why this is? Because when I test prev and prev2; it does seem to return the reversed linked list.

Answer 1

The reason for the error is that you cannot assume that both prev and prev2 are not None. Your while condition only guarantees that at least one of them is not None, but not both. So that means you still need to have a None check inside the body of the loop.

There are also some other issues:

• l1==[0]: is not correct. The left side of this comparison is a linked list instance, while the right side is a standard list. These comparisons will always be False, and so you can just omit them

• You are adding the carry to the wrong sum. You should add the carry from the previous iteration to the current sum, so things are currently happing in the wrong order.

• The resulting list should be reversed. You can do this on the fly by prefixing each node to l3, instead of appending it. This will also make it unnecessary to create a dummy ListNode(0) before the final loop. You can just start with None.

• Your code mutates the original input lists. This will be acceptable on code challenge sites, and be efficient, but it is bad practice. The caller should not be unpleasantly surprised that the lists they provide as input have been reversed by a call to this addTwoNumbers function. You can solve this in several ways, but it is probably easiest to reverse them a second time to undo that operation.

• To avoid repetition of code, you should create a reverse function

I'll assume that the ListNode constructor can take a second argument for initialising its next reference:

class ListNode:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

Then the corrected code could be:

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        def reverse(lst: ListNode):
            prev = None
            node = lst
            while node:
                curr = node.next 
                node.next = prev
                prev = node
                node = curr            
            return prev

        #Reversing both linked lists l1 & l2
        l1 = reverse(l1)
        l2 = reverse(l2)

        #Creating a new linked list that is the addition of the two reversed linked list
        node1 = l1
        node2 = l2
        l3 = None
        carry = 0 

        while node1 or node2:
            added = carry  # The carry from the previous iteration should be used
            if node1:  # You must have this check
                added += node1.val
                node1 = node1.next
            if node2:
                added += node2.val
                node2 = node2.next
            carry = added // 10  # Simpler way to get the carry
            l3 = ListNode(added % 10, l3)  # Prefix(!) the new node

        if carry == 1:
            l3 = ListNode(1, l3)

        # Restore the input lists:
        reverse(l1)  
        reverse(l2)
        return l3

Further remarks

Concerning the prefixing of nodes into the final list l3:

This is the main statement for doing that:

l3 = ListNode(added % 10, l3)

Let's break this down:

The constructor is called with two arguments:

• val = added % 10: this is one digit, so in case added is 14, this expression will evaluate to just 4 (the 1 will go to the carry).
• nxt = l3: this is the current (incomplete) list. The first time it is None.

The constructor then assigns these values as attributes of the new node that is being initialised:

self.val = val
self.next = nxt

So here we see that the value of nxt, is assigned to the new node's next attribute. As we passed l3 as argument, we are actually doing:

self.next = l3

By that statement we effectively prefix the new node to the list: the new node becomes the first node of the list. Moreover, self acts as the head of that list, which is now one node longer. We want to keep track of this new head, and so we assign the new node back to l3:

l3 = ListNode(added % 10, l3)

As the first time l3 was None, this will just create a one-node list, whose next attribute is that None. But the second time this is executed, we get a new node whose next refers to the "existing" node, so now we have a list of two... etc.

Sometimes it can come in handy to start a linked list with a dummy node like ListNode(0), which then later can be removed. However, in this revised algorithm that would not help, and so we start with None, which after the first iteration of the loop will serve as second argument to the ListNode constructor, which in turn will use it to initialise the next attribute of the new node. This new node will remain the tail of the list as other nodes are prefixed to it.