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'

also, merge_lists is outside the class LinkedList, I am assuming — daltonfury42
– daltonfury42, Commented Jul 21, 2019 at 9:23

Peter Nazarenko · Accepted Answer · 2019-07-27 21:51:49Z

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()

edited Jul 27, 2019 at 21:51

answered Jul 26, 2019 at 20:47

Peter Nazarenko

4111 gold badge7 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Avi Over a year ago

Thanks, @PeterNazarenko, Is there a way to sort ascending instead of descending?

Peter Nazarenko Over a year ago

Yes, of course. You only need to change comparison operations from > to <. I had updated my answer.

Sunitha · Accepted Answer · 2019-07-21 09:32:29Z

1

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
>>>

answered Jul 21, 2019 at 9:32

Sunitha

12.1k2 gold badges23 silver badges23 bronze badges

1 Comment

Avi Over a year ago

Thanks @Sunitha, But it is not the required result. I want to make 2 sorted linked lists - one sorted linked list using the function I wrote. What changes I need to do to the code?

Peter Nazarenko · Accepted Answer · 2019-07-21 18:59:04Z

1

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?

edited Jul 21, 2019 at 18:59

answered Jul 21, 2019 at 10:34

Peter Nazarenko

4111 gold badge7 silver badges16 bronze badges

4 Comments

Avi Over a year ago

Thanks, @PeterNazarenko! How can I make it a solution to my main problem?

Peter Nazarenko Over a year ago

@Avi 1. Do you really want to use recursive function for list merging? 2. Do you really want to divide the list data and operation to two classes? I updated my answer.

Avi Over a year ago

Thanks again @PeterNazarenko, your solution works! I thought a recursive solution is more elegant and shorter than conventional one. Maybe I'm wrong. The only question is if there is a shorter or more efficient recursive or other solution for my task.

Peter Nazarenko Over a year ago

@Avi No, you are not wrong about recursive functions, they are more elegant really but sometimes capricious.

Collectives™ on Stack Overflow

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

3 Answers 3

2 Comments

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related