在 python 中将排序的链表合并到一个排序的链表时出错

Question

我有以下代码。我创建了 2 个链表(l1 和 l2(，我想将它们组合成一个排序的链表。我为此使用了递归函数merge_lists，但出现错误。

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)

这是我得到的错误：

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

我再次查看了此任务并得到了以下递归函数。

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

事实上，它比非递归的短三倍，而且确实更优雅。运行时，它会更改第一个参数指定的列表。该类取自我前面的示例。该函数针对第一个列表比第二个列表长、短、其任何节点大于第二个列表的任何节点(反之亦然(的情况进行测试。

UPD - 按升序排序的递归合并列表：

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

您的 merge_lists 函数的实现方式是接受 2 个节点作为输入。因此，只需将merge_lists(l1, l2)更改为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
>>> 

Answer 3

对不起，我没有评论的名声，所以我写的是一个答案。我认为，Sunitha 的意思是，您不需要在函数merge_lists定义中使用.cur_node，而是在函数调用中使用。在这种情况下，函数参数将是类型Node，而不是LinkedList，并且您的问题中提到的错误将被消除。但在这种情况下，您也会收到错误，因为函数merge_lists将返回节点，而不是列表，例如，list_print()的调用不适用于返回的值。您可以使用下一个代码克服此错误：

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

但是，当然，它仍然不是您主要问题的解决方案。

UPD
我推荐以下解决方案(我认为它稍微简单一些(，其中包含单个类和全局合并函数(如上所述(。

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

当然，递归解决方案可以更短、更有吸引力，但它会更可靠吗？