Search code examples
pythonpython-3.xrecursiondata-structuresmergesort

Why does mergesort not work if I pass slow.next instead of mid?


In this code for mergesort, why can you pass mid but not slow.next directly in the recursive call to sortList? in line number 13, How is passing mid = slow.next different than directly passing 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

Solution

  • You first assigned slow.next to mid, so mid now holds the start of the second part of your list. Then you assigned None to slow.next, so if you now call self.sortList(slow.next), the second part of the list would not be sorted.

    If you call self.sortList(mid), then because mid is the pointer to the second part of the list, the mergesort works.