用于链接列表的Mergesort的Python实现不起作用 [英] Python implementation of Mergesort for Linked list doesn't work

问题描述

我在任何地方都找不到在Linked Lists的Python中实现Merge Sort的简单实现.这是我尝试过的:

I couldn't find a simple implementation of Merge Sort in Python for Linked Lists anywhere. Here's what I tried:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None 

合并排序实现:

def mergeSortLinkedList(A):
    # Base case length of 0 or 1:
    if A == None or A.next == None:
        return A

    leftHalf, rightHalf = splitTheList(A)

    mergeSortLinkedList(leftHalf)
    mergeSortLinkedList(rightHalf)

    # The above two lines should be modified to the following. Thanks to the answers.

    # leftHalf  = mergeSortLinkedList(leftHalf)
    # rightHalf = mergeSortLinkedList(rightHalf)

    return mergeTheLists(leftHalf, rightHalf)

拆分:

def splitTheList(sourceList):
    if sourceList == None or sourceList.next == None:
        leftHalf = sourceList
        rightHalf = None

        return leftHalf, rightHalf

    else:
        midPointer = sourceList
        frontRunner = sourceList.next
        # totalLength += 1        - This is unnecessary

        while frontRunner != None:
            frontRunner = frontRunner.next

            if frontRunner != None:
                frontRunner = frontRunner.next
                midPointer = midPointer.next

    leftHalf = sourceList
    rightHalf = midPointer.next
    midPointer.next = None

    return leftHalf, rightHalf

合并:

def mergeTheLists(leftHalf, rightHalf):
    fake_head = ListNode(None)
    curr = fake_head

    while leftHalf and rightHalf:
        if leftHalf.val < rightHalf.val:
            curr.next = leftHalf
            leftHalf = leftHalf.next

        else:
            curr.next = rightHalf
            rightHalf = rightHalf.next

        curr = curr.next

    if leftHalf == None:
        curr.next = rightHalf

    elif rightHalf == None:
        curr.next = leftHalf

    return fake_head.next

数据:

# Node A:
nodeA1 = ListNode(2)

nodeA2 = ListNode(1)
nodeA1.next = nodeA2

nodeA3 = ListNode(9)
nodeA2.next = nodeA3

nodeA4 = ListNode(3)
nodeA3.next = nodeA4

# Node C:
nodeC1 = ListNode(5)
nodeA4.next = nodeC1

nodeC2 = ListNode(6)
nodeC1.next = nodeC2

nodeC3 = ListNode(4)
nodeC2.next = nodeC3

nodeC4 = ListNode(5)
nodeC3.next = nodeC4

调用mergeSortLinkedList(nodeA1)时的预期输出:

1 2 3 4 5 5 6 9

我得到以下信息:

2 5 6 9

我无法弄清楚小姐在哪里.请帮忙.

I am unable to figure out where the miss is. Please help.

推荐答案

您不使用递归调用的返回值.该代码应为:

You don't use the return values from the recursive call. The code should be:

def mergeSortLinkedList(A):
    if A is None or A.next is None:
        return A

    leftHalf, rightHalf = splitTheList(A)

    left = mergeSortLinkedList(leftHalf)
    right = mergeSortLinkedList(rightHalf)

    return mergeTheLists(left, right)

在调用函数之后，在某些情况下，该参数不指向排序列表的开头.

After the call of the function, the argument in some cases doesn't point to the head of the sorted list.

代码中的下一个错误是未定义变量totalLength的使用.

The next bug in the code is usage of undefined variable totalLength.

这篇关于用于链接列表的Mergesort的Python实现不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！