如果我传递 slow.next 而不是 mid，为什么合并排序不起作用？

Question

这段mergesort的代码，为什么在递归调用sortList时可以直接传mid，而不能直接传slow.next？在第 13 行中，传递 mid = slow.next 与直接传递 slow.next?

有何不同

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        fast = head.next
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow.next
        slow.next = None
        l = self.sortList(head)
        r = self.sortList(slow.next)##instead pass mid here, and it works.
        return self.merge(l,r)
    
    def merge(self, l, r):
        if not l or not r:
            return l or r
        if l.val > r.val:
            l, r = r, l
        # get the return node "head"
        head = pre = l
        l = l.next
        while l and r:
            if l.val < r.val:
                l = l.next
            else:
                nxt = pre.next
                pre.next = r
                tmp = r.next
                r.next = nxt
                r = tmp
            pre = pre.next
        # l and r at least one is None
        pre.next = l or r
        return head

Answer 1

您首先将 slow.next 分配给了 mid，因此 mid 现在占据了列表第二部分的开头。然后你将 None 分配给 slow.next，所以如果你现在调用 self.sortList(slow.next)，列表的第二部分将不会被排序。

如果调用 self.sortList(mid)，那么因为 mid 是指向列表第二部分的指针，所以合并排序有效。