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

此回复适用于较早版本的代码。请参阅我对新版本代码修复的新回复。

好的，看起来问题出在您从函数 returning 链表的方式上。在 front_to_back_split 中，您分配给 head1 和 head2，但这些只是函数的参数。即，它们是局部变量。分配给它们对调用者没有影响。

一个更好的方法是去掉 head1 和 head2 作为参数，而是让它们成为普通的局部变量。然后将其更改为 return head1 和 head2，像这样：

return head1, head2

那么，在merge_sort中，就不再需要分配a和b了。相反，您可以这样做：

a, b = front_to_back_split(head)

同样，merge_sort 应该 return 新的 head 以便调用者可以使用它。否则调用者无法确定新列表头是什么。

Answer 2

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

在 merge_sort 的顶部有一个光秃秃的 return。将其更改为：
```
return head
```
在merge_sort中，改变递归调用，使它们更新a和b，如下：
```
a = merge_sort(a)
b = merge_sort(b)
```
在您的主要代码中，对列表进行排序后，您需要一个带有新头的 LinkedList 才能打印它，因为 llist1 仍将指向旧头头。你可以使用这个：
```
print "Sorted list"
new_head = merge_sort(llist1.head)
new_list = LinkedList()
new_list.head = new_head
new_list.print_list()
```

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

Merge Sort for linked list implementation in python is not working

python

sorting

data-structures

mergesort

合并两个排序列表

拆分链表

合并排序

主要