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)）并向我展示如何递归调用它，我将非常感激。提前谢谢您。 此外，为了将链表分成两半，我应该使用函数divide(self)，但如果您知道其他方法，请告诉我。

- Yondaru

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)

- Tom Kealy