递归合并在python的链表上排序

Question

我想问你一些关于这个项目的帮助我正在研究我在哪里写递归合并排序函数，它将在链表上工作。这就是我迄今为止的（我没有把整个代码放在这里，只是我正在努力的部分）。

.... 
    def merge_sort(self): 
     len_list,len_list2= 0, 0 
     list=self.head   #first half of linked list 
     list2=self.divide() #function that makes second half of linked list   
     #from imput like z = SortedList([46, 27, 93, 91, 23]) 
     #i will get list=46->27->93->None 
     #   list2=91->23-> 
     while list is not None: 
      len_list+=1 
      list=list.next 
     while list2 is not None: 
      len_list2+=1 
      list2=list2.next 
     # in len_list,len_list2 i am storing length of these linked lists 

     def merge(self,left,right): 
      result,i,j=None,0,0 
      while (i<len_list) and (j<len_list2): 
       if list.data < list2.data: 
        result.append(list.data) #append is function which appends 
        list=list.next   #nodes    
        i+=1 
       else: 
        result.append(list2.data) 
        list2=list2.next 
        j+=1 
       #some returns should follow but i dont know what to do 

我很确定这是错误的很多级别我只是试图复制列表的合并排序功能，并将其转换到链接列表上。如果任何人都可以帮助我如何做到这一点，而不需要将定义的参数改为（def merge_sort（self）），并告诉我如何递归地调用它，我将非常感激。事先谢谢你。 同时适用于半区我应该使用功能区划（个体经营）使链表但如果你知道任何其他方式让我知道

Answer 1

一般list.head实现，这样它会返回一个参考列表的第一个元素，而不是名单的前半部分。也许这将是更好地执行list.divide（）返回拖名单：

left_half, right_half = self.divide() 

更妙的是，也许更Python，将是你的LinkedList类中，实现的方法__getitem__和__len__。

喜欢的东西：

def __len__(self): 
    return len(self.list) 

def __getitem__(self, position): 
    return self.list(position) 

第一个允许您快速到达长度，第二个将允许您切片项目。

合并排序的基本结构是：

def merge_sort(list): 
    #Check the list doesn't have 1 item 
    if len(list) == 1: 
     return list 
    #Find the middle of the list 
    middle = len(list)//2 

    #Find the left and right halfs via slicing 
    left = list(:middle) 
    right = list(middle:) 

    #Recursively sort your lists 
    left = merge_sort(left) 
    right = merge_sort(right) 

    #Merge them together 
    return LinkedList(merge(left, right)