遞歸合併在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)