递归合并在python中链接列表上排序

i would like to ask you for help with this project i am working on where i have to write recursive merge sort function that will work on linked lists.this is what i have so far(i didnt put whole code here just the part i am struggling with).

我想请求你帮助这个项目,我正在努力在哪里我必须编写递归合并排序功能,将在链表上工作。这是我到目前为止(我没有把整个代码放在这里只是我的部分)挣扎着)。

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

I am pretty sure this is wrong on many levels I was just trying to copy Merge sort function for Lists and convert it on Linked lists. If anyone can help me how to do this, without changing arguments of definitions as( def merge_sort(self)) and show me how to recursively call it, I would appreciate it a lot. Thank you beforehand. Also for making linked lists in halfs i should use function divide(self) but if you know any other way let me know

我很确定这在许多层面都是错误的我只是想复制列表的合并排序功能并将其转换为链接列表。如果有人可以帮我怎么做,不改变定义的参数(def merge_sort(self))并告诉我如何递归调用它,我会很感激。先谢谢你了。另外,为了制作一半的链表,我应该使用功能除(自我),但如果你知道其他任何方式让我知道

1 个解决方案

#1

Generally list.head is implemented so that it will return a reference to the first element of your list, and not the first half of the list. Maybe it would be better to implement list.divide() to return tow lists:

通常实现list.head,以便它将返回对列表的第一个元素的引用,而不是列表的前半部分。也许最好实现list.divide()来返回两个列表:

left_half, right_half = self.divide()

Even better, and maybe more pythonic, would be in your LinkedList class, implement the methods __getitem__ and __len__.

甚至更好,也许更pythonic,将在您的LinkedList类中,实现方法__getitem__和__len__。

Something like:

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

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

The first allows you to get the length quickly, the second will allow you to slice items.

第一个允许你快速获得长度,第二个允许你切片项目。

The basic structure of merge sort is:

合并排序的基本结构是:

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)

#1