python - 如果我通过 slow.next 而不是 mid 为什么合并排序不起作用？

Question

在合并排序的这段代码中，为什么可以在对 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

标签： pythonpython-3.xrecursiondata-structuresmergesort

Answer 1

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

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