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

合并两个排序列表

def merge_lists(head1, head2):

   if(head1 is None):
      return head2
   if(head2 is None):
      return head1

   s = t= LinkedList.Node(None)

   while(head1 and head2):
     if(head1.data <= head2.data):
        c= head1
        head1 = head1.next
     else:
        c= head2
        head2 = head2.next

     t.next = c 
     t = t.next
  t.next = head1 or head2
  return s.next

分割链表

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 和 head2，但这些只是函数的参数。即，它们是局部变量。分配给它们对调用者没有影响。

更好的方法是消除 head1 和 head2 作为参数，而只是将它们设为普通的局部变量。然后将其更改为返回 head1 和 head2，如下所示:

return head1, head2

然后，在merge_sort中，您不再需要分配a和b。相反，你可以这样做:

a, b = front_to_back_split(head)

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