Mergesort for Linklist 的 Python 实现不起作用

Question

我在任何地方都找不到Linked Lists的Python中Merge Sort的简单实现。以下是我尝试过的：

单链表的定义：

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

我不知道小姐在哪里。请帮忙。

Answer 1

您不使用递归调用的返回值。代码应该是：

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)

在调用函数之后，在某些情况下，参数不会指向排序列表的头部。

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