CODEWITHSUNDEEP
pythonalgorithmdata-structureslinked-list
Arvind Sangwan
Arvind Sangwan

Reputation: 23

After merging two sorted linked list None gets appended at end of newly constructed list

Node class is being used to create node and linklist printing and merge2LinkLists methods are helper functions.

I am iterating and checking from each list to ensure both 2 sorted linkedlists are merged to form a new list.

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
        self.tail = None

    def printLinkList(self):
        curr = self.head
        while(curr):
            print(curr.data, end=" ")
            curr = curr.next



    def addLast(self,value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            return
        else:
            head = self.head
            while(head.next):
                head = head.next

            head.next = new_node

     def merge2LinkedList(self,l1,l2):
        mergedList = LinkedList()
        head1 = l1.head
        head2 = l2.head

        while(head1 != None and head2 !=None):
            if(head1.data < head2.data):
                mergedList.addLast(head1.data)
                head1 = head1.next
            else:
                mergedList.addLast(head2.data)
                head2 = head2.next

        while(head1 != None):
            mergedList.addLast(head1.data)
            head1 = head1.next

        while (head2 != None):
            mergedList.addLast(head2.data)
            head2 = head2.next

        print(mergedList.printLinkList())


list = LinkedList()
list.addLast(2)
list.addLast(4)
list.addLast(5)
list.addLast(6)
list.addLast(90)

list2 = LinkedList()
list2.addLast(3)
list2.addLast(7)
list2.addLast(40)
list2.addLast(45)
list2.addLast(80)

list.merge2LinkedList(list,list2)

Output:

2 3 4 5 6 7 40 45 80 90 None

Upvotes: 0

Views: 31

Answers (1)

Daniel
Daniel

Reputation: 42758

You are printing the return value of printLinkList, which is None.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def print(self):
        curr = self.head
        while curr:
            print(curr.data, end=" ")
            curr = curr.next
        print()

    def add(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            head = self.head
            while head.next:
                head = head.next
            head.next = new_node

def merge_linked_lists(l1, l2):
    merged_list = LinkedList()
    head1 = l1.head
    head2 = l2.head

    while head1 is not None and head2 is not None:
        if head1.data < head2.data:
            merged_list.add(head1.data)
            head1 = head1.next
        else:
            merged_list.add(head2.data)
            head2 = head2.next

    while head1 is not None:
        merged_list.add(head1.data)
        head1 = head1.next

    while head2 is not None:
        merged_list.addLast(head2.data)
        head2 = head2.next

list = LinkedList()
list.add(2)
list.add(4)
list.add(5)
list.add(6)
list.add(90)

list2 = LinkedList()
list2.add(3)
list2.add(7)
list2.add(40)
list2.add(45)
list2.add(80)

merged_list = merge_linked_lists(list, list2)
merged_list.print()

Upvotes: 2

Related Questions