CODEWITHSUNDEEP
pythonlinked-listsingly-linked-list
Mo Fatah
Mo Fatah

Reputation: 169

Error: Merge two sorted linkedlist using dummy head technique in Python

I'm trying to solve merge two sorted linkedlist problem using dummy head technique. For some reason I have an error coming from passing an argument to my dummy head holder. The output suppose to merge both linkedlist like this: 1-> 1-> 2-> 3-> 7-> None

I would be happy if you please guide which data needs to pass in my dummy head variable? Thanks in advance! This is the error I have:

    dummy = LinkedList()
TypeError: __init__() missing 1 required positional argument: 'data

Here's my complete code:


class LinkedList:
    def __init__(self, data):
        self.data = data
        self.next = None


def print_list(head: LinkedList) -> None:
    while head:
        print(head.data, end=" -> ")
        head = head.next
    print("None")


def merge_lists(headA, headB):
    dummy = LinkedList()
    curr = dummy

    while headA != None and headB != None:
        if headA.data < headB.data:
            curr.next = headA
            headA = headA.next
        else:
            curr.next = headB
            headB = headB.next

        curr = curr.next

    if headA != None:
        curr.next = headA
    else:
        curr.next = headB

    return dummy.next



node1 = LinkedList(1)
node1.next = LinkedList(2)
node1.next.next = LinkedList(7)


node2 = LinkedList(1)
node2.next = LinkedList(3)

print(merge_lists(node1, node2)) # 1-> 1-> 2-> 3-> 7-> None

Upvotes: 0

Views: 198

Answers (2)

spider_Malaya
spider_Malaya

Reputation: 13

class node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class linkedList:
    def __init__(self):
        self.head = None
        
    def insertNode(self, data):
        newnode = node(data)
        
        if self.head is None:
            self.head =  newnode
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = newnode
    def printLL(self):
        
        current = self.head
        while current.next is not None:
            print(current.data, end='----->')
            current = current.next
        print(current.data, '------>None')
    def sortLL(self):
        arr=[]
        current = self.head
        while current.next is not None:
            arr.append(current.data)
            current = current.next
        arr.append(current.data)
        arr.sort()
        self.head = None
        
        for i in arr:
            self.insertNode(i)
            
def mergeTwoSortedLL(l, l2):
    
    current1 = l.head
    current2 = l2.head
    l3 = linkedList()
    
    while current1 is not None and current2 is not None:
        
        if current1.data < current2.data:
            l3.insertNode(current1.data)
            current1 = current1.next
        else:
            l3.insertNode(current2.data)
            current2 = current2.next
            
    if current1 is None:
        
        while current2.next is not None:
            l3.insertNode(current2.data)
            current2 = current2.next
        l3.insertNode(current2.data)
    else:
        while current1.next is not None:
            l3.insertNode(current1.data)
            current1 = current1.next
        l3.insertNode(current1.data)
        
    return l3

        
        
    
    
                 
                           
    
    
    
            
l = linkedList()
l.insertNode(9)
l.insertNode(18)
l.insertNode(11)
l.insertNode(15)
l.insertNode(1)
l.insertNode(8)
l.sortLL()
l.printLL()
l2 = linkedList()
l2.insertNode(9)
l2.insertNode(18)
l2.insertNode(11)
l2.insertNode(15)
l2.insertNode(1)
l2.insertNode(8)
l2.sortLL()
l2.printLL()
mergeTwoSortedLL(l,l2).printLL()

Upvotes: 1

trincot
trincot

Reputation: 350365

Since it is a dummy node, and you never ever use the data attribute of that node, you can pass anything as argument, like None:

dummy = LinkedList(None)

Alternatively, you could specify that providing an argument is optional, and define the constructor as follows:

class LinkedList:
    def __init__(self, data=None):
        self.data = data
        self.next = None

Unrelated, but at the end of your script you have:

print(merge_lists(node1, node2))

This will print the object reference. You probably wanted to call the function you have defined for this purpose:

print_list(merge_lists(node1, node2))

If you want print to work like that, then instead of the print_list function, enrich LinkedList with an __iter__ method to ease iteration over the values in the list, and a __repr__ or __str__ method as follows:

class LinkedList:
    def __init__(self, data=None):
        self.data = data
        self.next = None

    def __iter__(self):
        head = self
        while head:
            yield head.data
            head = head.next
        yield None  # Optional

    def __repr__(self):
        return " -> ".join(map(str, self))

...and then you can do

print(merge_lists(node1, node2))

Upvotes: 1

Related Questions