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
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.