@juilacoco To return the merged head
How can it be n log(n) while it has to navigate form the beginning to n to device a list into two?
@ZekunWang hn is not dynamically allocated on the heap, so there's no need to free.
I can't understand your code.
@xysrGeeemm there are two pointers, slow and fast, when fast reach end, the slow just reach the mid, that is the p1. the code just spilt input list to two sub list by using this method. this is my thoughts.
Can someone explain to me this line?
tail.next, tail, h1 = h1, h1, h1.next.
It seems that the second tail = h1 already overwrite what the first assignment did. Therefore no matter what the first assignment did, tail would eventually become h1. Is this correct?
Helpful explanation of space complexity and your solution.
what do you mean by auto variable? Why it can avoid memory leak?
I can't understand your function about sortList(),would you please explain it for me ?
Hi, arindamkhaled. Thank you for your remind. I forget to consider the space of the function call stack.
Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example
I can't understand your code,can you explain it for me?
@caikehe said in Python merge-sort with comments.:
head = pre = l
what does pre do
I just think quick sort will cost O(log N) space.
the space complexity of the quick sort is O(nlogn) only if it is the array, and it should be constant here, for ListNode.
May I ask you why not divide the list from the beginning?Such as divide[1,4,2,3,7] into [1,4] &[2,3,7];and then divide[2,3,7] into [2,3]&
But that basically violates the requirement of constant space.
To be constant space, we need to do it iteratively.
E.g. bottom-up mergesort.
There is a fancy term -- it is called Short-circuit evaluation. And yes, it is supported in both C++ and Java.
No one has replied
Disabled Categories are greyed out
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.