我想请你帮助我正在做的这个项目，我必须编写递归合并排序函数，它将在链接列表上工作。这是我到目前为止所拥有的(我没有把整个代码放在这里只是我正在努力的部分)。
....
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) 但如果您知道任何其他方式，请告诉我
最佳答案
通常 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)
关于python - python中链表的递归合并排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30129552/