Python链表归并排序getMiddle函数陷入无限循环求助

你的代码核心问题出在sortList方法中错误地使用了链表实例的self.head而非传入的head参数，导致递归拆分链表时永远在操作原链表的头节点，无法正确拆分到单个节点，最终引发无限递归，进而让getMiddle函数陷入循环。

具体修复点： #

1. 终止条件修正：将sortList里的终止条件从判断self.head改为判断传入的head参数，确保递归能正确终止。
2. 子链表头节点赋值修正：拆分链表时，left应该是当前传入的head，而非原链表的self.head。
3. 递归调用参数修正：递归排序左右子链表时，传入拆分后的left和right，而非依赖self.head。
4. 更新链表头节点：排序完成后，需要将sortList返回的新头节点赋值给链表的self.head，否则原链表头不会更新，打印结果还是旧数据。

修复后的完整代码： #

# node class 
class Cat:
    def __init__(self, name="", next=None):
        self.name = name
        self.next = next

# linked list class
class LinkedList:
    def __init__(self):
        self.head = None
   
    def pushCat(self, new_name):       # add new node to beginning of LL
        newCat = Cat(new_name, None)
        
        if self.head is None:          # if LL empty, set new node to head 
            self.head = newCat
        else:
            newCat.next = self.head   
            self.head = newCat

    # split list down to individual elements
    def sortList(self, head):
        # 修正：判断传入的head而非self.head
        if not head or not head.next:
            return head

        left = head  # 修正：使用传入的head作为当前子链表的头
        mid = self.getMiddle(head)
        right = mid.next
        mid.next = None

        # 修正：递归传入拆分后的左右子链表头
        left = self.sortList(left)
        right = self.sortList(right)

        return self.mergeList(left, right)
    
    # merge list
    def mergeList(self, list1, list2):
        dummy = tail = Cat()

        while list1 and list2:
            if list1.name < list2.name:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        # append any extra elements
        if list1:
            tail.next = list1
        if list2:
            tail.next = list2
        
        return dummy.next      #return head

    def getMiddle(self, head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow
    
    def printList(self):
        curr_node = self.head
        while curr_node:
            print(curr_node.name, end = " ")
            curr_node = curr_node.next
        print("\n")

# create linked list, push 3 new cats, and call sortlist() function to mergesort alphabetically.
if __name__ == '__main__':
    li = LinkedList()

    li.pushCat("Roland")
    li.pushCat("Billy")
    li.pushCat("Caesar")

    head = li.head
    print(head.name)

    print("Before sort: ")
    li.printList()          # Caesar Billy Roland
    # 修正：将排序后的新头赋值给链表的head
    li.head = li.sortList(head)
    print("After sort: ")   # expected: Billy Caesar Roland
    li.printList()          # 现在输出正确结果

修复后运行结果： #

Caesar
Before sort: 
Caesar Billy Roland 

After sort: 
Billy Caesar Roland 

内容的提问来源于stack exchange，提问作者user19575565