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

我很确定这在很多层面上都是错误的，我只是想复制列表的合并排序函数并将其转换为链表。如果有人能帮助我如何做到这一点，而不改变定义的参数 as( def merge_sort(self)) 并告诉我如何递归调用它，我将非常感激。预先谢谢你。另外，为了将链表分成两半，我应该使用函数 divide(self) 但如果您知道任何其他方式，请告诉我

Answer 1

通常 list.head 的实现是为了返回对列表第一个元素的引用，而不是列表的前半部分。也许实现 list.divide() 以返回两个列表会更好:

left_half, right_half = self.divide()

在您的 LinkedList 类中，实现方法 __getitem__ 和 __len__ 会更好，也许更像 pythonic。

类似于:

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)