Error in merging sorted linked lists to one sorted linked list in python

Question

I have the following code. I create 2 linked lists (l1 and l2) and I would like to combine them together to one sorted linked list. I use the recursive function merge_lists for this and I get error.

class Node(object):
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node


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

    def add_node(self, data):
        new_node = Node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node #  set the current node to the new one.

    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print (node.data)
            node = node.next

def merge_lists(h1, h2):
        if h1 is None:
            return h2
        if h2 is None:
            return h1

        if (h1.data < h2.data):
            h1.next = merge_lists(h1.next, h2)
            return h1
        else:
            h2.next = merge_lists(h2.next, h1)
            return h2



l1 = LinkedList()
l1.add_node(1)
l1.add_node(5)
l1.add_node(7)

ll.list_print()

l2= LinkedList()
l2.add_node(2)
l2.add_node(6)
l2.add_node(8)
l2.list_print()

merge_lists(l1, l2)

Here is the error I get:

7
5
1
8
6
2

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-59-5032e795cb05> in <module>()
     49 l2.list_print()
     50 
---> 51 merge_lists(l1, l2)

<ipython-input-59-5032e795cb05> in merge_lists(h1, h2)
     27             return h1
     28 
---> 29         if (h1.data < h2.data):
     30             h1.next = merge_lists(h1.next, h2)
     31             return h1

AttributeError: 'str' object has no attribute 'data'

Answer 1

I reviewed this task again and got the following recursive function.

class List1(object):
    ...
    ...
    def merge_lists(self, h1, h2):
      if h1!= None and h2 != None:   # l2 != None works in case of any node of the 1st list is smaller then any node of the 2nd list
          if h2.data > h1.data:
              cur = self
              while h2 and h2.data > h1.data:
                  self.add_node(cur, h2.data)
                  cur = cur.next
                  h2 = h2.next
          if h1.next is None:
              h1.next = h2  # works in case of any node of the 1st list is bigger then any node of the 2nd list
          else:
              h1.merge_lists(h1.next, h2)
# end of class

l1 = List1()
l1.add_node(l1, 1)
l1.add_node(l1, 5)
l1.add_node(l1, 7)
l1.list_print()
print()

l2 = List1()
l2.add_node(l2, 2)
l2.add_node(l2, 6)
l2.add_node(l2, 8)
l2.add_node(l2, 15)
l2.add_node(l2, 20)
l2.list_print()
print()

l1.merge_lists(l1.next, l2.next)  # Test
l1.list_print()

Indeed, it is about three times shorter than non-recursive and really more elegant. When running, it changes the list specified by the first argument. The class is taken from my previous example. The function is tested for cases when the first list is longer than the second, when it is shorter, when any of its node is larger than any node of the second list and vice versa.

UPD - Recursive merging lists sorted in the ascending order:

class List1(object):
...
...
    def merge_lists_ascend(self, h1, h2):
      if h1!= None and h2 != None:
          if h2.data < h1.data:  # '<' for ascending ordered lists
              cur = self
              while h2 and h2.data < h1.data:  # '<' for ascending ordered lists
                  self.add_node(cur, h2.data)
                  cur = cur.next
                  h2 = h2.next
          if h1.next is None:
              h1.next = h2
          else:
              h1.merge_lists_ascend(h1.next, h2)
# end of class

l11 = List1()
l11.add_node(l11, 7)
l11.add_node(l11, 5)
l11.add_node(l11, 1)
l11.list_print()
print()

l21 = List1()
l21.add_node(l21, 20)
l21.add_node(l21, 16)
l21.add_node(l21, 8)
l21.add_node(l21, 6)
l21.add_node(l21, 2)
l21.list_print()
print()

l11.merge_lists_ascend(l11.next, l21.next)  # Test
l11.list_print()

Answer 2

Excuse me, I have no reputation for comment, so I'm writing is an answer. I think, Sunitha meant that you need to use .cur_node not in the function merge_lists definition but in the function call. In this case function arguments will be of type Node, not LinkedList, and mentioned in your question error will be eliminated. But also in this case you'll get an error because the function merge_lists will return a node, not a list, and for example the call of the list_print() will not be applicable for the returned value. You can overcome this error with the next code:

l3=LinkedList()
l3.cur_node=merge_lists(l1.cur_node, l2.cur_node)
l3.list_print()

But, of course, it's still not a solution for your main problem.

UPD
I recommend the following solution (I think it's slightly simpler) with the single class and the global merge function (as above).

class List1(object):
    def __init__(self, a = 0):
        self.data = a
        self.next = None

    def add_node(self, prev, a):
        q = List1(a)
        q.next = prev.next
        prev.next = q

    def list_print(self):
        q=self.next
        while q != None:
            print(q.data)
            q=q.next
# end of class

def merge_lists2(h1, h2):
    node1 = h1.next
    node2 = h2.next
    list = List1()
    q = list.next
    while node1 or node2:
        if node1 and node2 and node1.data > node2.data:
            if q:
                list.add_node(q, node1.data)  # Add a node to the end of a list
                q = q.next                    # End of a list moves to tne new position
            else:
                list.add_node(list, node1.data)  # Add a node to the beginning of a list (after the leading node)
                q = list.next                    # New end position
            node1 = node1.next
        elif node1 and node2 and node1.data <= node2.data:
            if q:
                list.add_node(q, node2.data)
                q = q.next
            else:
                list.add_node(list, node2.data)
                q = list.next
            node2 = node2.next
        if node1 == None and node2:  # If the 1st list finished first
            while node2:
                if q:
                    list.add_node(q, node2.data)
                    q = q.next
                node2 = node2.next
        if node2 == None and node1:  # If the 2nd list finished first
            while node1:
                if q:
                    list.add_node(q, node1.data)
                    q = q.next
                node1 = node1.next
    return list

l1 = List1()
l1.add_node(l1,1)
l1.add_node(l1,5)
l1.add_node(l1,7)

l1.list_print()
print()

l2 = List1()
l2.add_node(l2,2)
l2.add_node(l2,6)
l2.add_node(l2,8)
l2.add_node(l2,15)  # Extra nodes for testing purpose
l2.add_node(l2,20)

l2.list_print()
print()

l3 = List1()
l3 = merge_lists2(l1, l2)
print()
l3.list_print()

Of course, a recursive solution can be much shorter and more attractive, but will it be more reliable?

Answer 3

Your merge_lists function is implemented in a way that it accepts 2 nodes as the inputs. So just change merge_lists(l1, l2) to merge_lists(l1.cur_node, l2.cur_node)

>>> merge_lists(l1.cur_node, l2.cur_node)    
<__main__.Node object at 0x7faf116dc9e8>
>>> l1.list_print()
7
5
1
8
6
2
>>>