python中链表实现的合并排序不起作用

Question

有人能帮我找出这个代码出了什么问题吗？代码正在打印链接列表中的第一个节点，而不是已排序的链接列表。在

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

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

    def push(self, new_data):
       new_node = self.Node(new_data)
       new_node.next = self.head
       self.head = new_node

    def print_list(self):
       temp = self.head
       while(temp):
          print temp.data
          temp = temp.next

合并两个已排序的列表

^{pr2}$

拆分链接列表

def front_back_split(head):
   if(head is None or head.next is None):
      head1 = head
      head2 = None
   else:
      slow = head
      fast = head.next
      while(fast != None):
         fast = fast.next
         if(fast!=None):
            slow = slow.next
            fast = fast.next

   head1 = head
   head2 = slow.next
   slow.next = None

   return head1, head2

合并排序

def merge_sort(head):
   if(head is None or head.next is None):
      return 

   a,b = front_back_split(head)


   merge_sort(a)
   merge_sort(b)

   new_head = merge_lists(a,b)

   return new_head

主

if __name__=='__main__':
   llist1 = LinkedList()
   llist1.push(6)
   llist1.push(7)
   llist1.push(1)
   llist1.push(4)
   llist1.push(3)
   llist1.push(8)



   print "Sorted list"
   new_head = merge_sort(llist1.head)
   llist1.print_list()

Answer 1

此响应适用于代码的早期版本。请参阅我的新响应，以获取新版本代码的修复。在

好的，问题是你从函数返回链表的方式。在front_to_back_split中，将赋值给head1和{}，但这些只是函数的参数。一、 它们是局部变量。分配给它们对调用者没有影响。在

更好的方法是消除head1和{}作为参数，而只将它们作为普通的局部变量。{{cd2>然后改成

return head1, head2

然后，在merge_sort中，您不再需要分配a和{}。相反，您只需：

^{pr2}$

类似地，merge_sort应该返回新的head，这样调用者就可以使用它了。否则，调用者无法确定新的列表头是什么。在

Answer 2

好的，我已经调试了你的更新版本，现在可以用了。有三个变化：

1. 在merge_sort的顶部有一个空的return。更改为：

   return head
   

2. 在merge_sort中，更改递归调用，使它们更新a和{}，如下所示：

   a = merge_sort(a)
   b = merge_sort(b)
   

3. 在主代码中，对列表排序后，需要一个带有新头的LinkedList才能打印它，因为llist1仍然指向旧的头。您可以使用这个：

   print "Sorted list"
   new_head = merge_sort(llist1.head)
   new_list = LinkedList()
   new_list.head = new_head
   new_list.print_list()