sum of two Linked Lists python --Problem from CTCI

Admin 1
Viewed 246

I am trying to run the below code, I expect the code to return a list called head which would contain sum of (first and second) where first and second is linked lists passed as an argument.

As you see at the end I have created two linked List l1 and l2. I am assuming this linked lists will inherit from the Node class.

But it gives an attribute error. I can't seem to figure out the problem. I am a novice in programming, self learner. What might be causing this error? How do we go about solving it?

class Node:                                  
    def __init__(self,data=None):            
        self.data = data                     
        self.next = None                     
                                             
class LinkedList:                            
    def __init__(self):                      
        self.head = None                     
                                             
    def display(self):                       
        elems = []                           
        current = self.head                  
        while current != None:               
            elems.append(current.data)       
            current = current.next           
        return elems                         
                                             
    def append(self, data):                  
        elem = Node(data)                    
        if self.head == None:                
            self.head = elem                 
        else:                                
            current = self.head              
            while current.next != None:      
                current = current.next       
            current.next = elem              
                                             
    def addTwoLists(self, first, second):    
        head = third = Node(0)               
        carry = 0                            
                                             
        while first or second or carry:      
            if first:                        
                carry += first.data          
                first = first.next           
            if second:                       
                carry += second.data         
                second = second.next         
                                             
            third.data = carry % 10          
            carry = carry // 10              
                                             
            if first or second or carry:     
                third.next = Node(0)         
                third = third.next           
        return head
                             
ll = LinkedList()             
list1 = LinkedList()          
list2 = LinkedList()          
list1.append(7)               
list1.append(1)               
list1.append(6)               
print(list1.display())        
list2.append(5)               
list2.append(9)               
list2.append(2)               
print(list2.display())        
ll.addTwoLists(list1,list2)   
print(ll.display())

And the error I get it:

  carry += first.data
AttributeError: 'LinkedList' object has no attribute 'data'
python
3 Answers

You need to make the distinction between a LinkedList and a Node.

I am assuming this linked lists will inherit from the Node class.

While they have a relation, it is not inheritance. The only connection between them is that LinkedList contains Nodes. Inheritance is achieved syntactically by doing something like: class LinkedList(Node):, but that seems logically improper in your case (LinkedList is not a Node, but it does contain a Node, as your current code does).

Using meaningful names to your variables can help with this confusions. Note that the arguments to addTwoLists are lists, but you treat them as if they were nodes with a data attribute.

Another thing you need to decide is if your function returns a new list or mutates one. I understand that you want to return a new one, in that case the method can either be static, or not inside the class at all (because you never really use self). Currently your method doesn't mutate any object and you also don't use its return value.

You can define it outside of the class and make it return a new list:

def addTwoLists(first_list, second_list):
    third_list = LinkedList()
    carry = 0

    first_node = first_list.head
    second_node = second_list.head
    while first_node or second_node or carry:      
        if first_node:                        
            carry += first_node.data          
            first_node = first_node.next           
        if second_node:                       
            carry += second_node.data         
            second_node = second_node.next         
                                         
        third_list.append(carry % 10)
        carry = carry // 10              
                                                   
    return third_list

Then in your main code, just do ll = addTwoLists(list1, list2)

user_60458000

First is a linkedList object so it can not have attributes from the Node Class. If you want to make First a Node Object you have to use

First = Node()
user_138277530

if you want to acces the data then do this it will reolve your current error. Let me know if you didnt understand what i mean

first_node = first.head
print(first_node.data)
user_121626080
Related