Блог

Почему в этом коде для сортировки слиянием вы можете передать mid, но не slow.next непосредственно в рекурсивном вызове sortList ? в строке номер 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
  

Вы сначала назначили slow.next mid , поэтому mid теперь содержит начало второй части вашего списка. Затем вы назначили None slow.next , поэтому, если вы сейчас вызовете self.sortList(slow.next) , вторая часть списка не будет отсортирована.

Если вы вызываете self.sortList(mid) , то, поскольку mid это указатель на вторую часть списка, сортировка слиянием работает.