class Solution(object): def sortList(self, head): """ :type head: ListNode :rtype: ListNode """ h=head vals= while h!=None: vals.append(h.val) h=h.next`enter code here` vals.sort() h1=head count=0 while h1!=None: h1.val=vals[count] count+=1 h1=h1.next return head
I thinks that it would better to use heapq instead of list like below if use O(n) space
import heapq as hq h =  cursor = head while cursor: hq.heappush(h, cursor.val) cursor = cursor.next cursor = head while cursor: cursor.val = hq.heappop(h) cursor = cursor.next return head
@laeshiny Why do you think that's better?
@StefanPochmann I though like below:
list (Average : Worst)
Append : O(n) : O(n) (append n count)
Sort : O(n log n) : O(n log n)
heapq (Average : Worst)
Insert : O(n) : O(n log n) (insert n count)
In the worst case list and heaqp are similar but in the average case list is slower than heapq.
So, I think that using heapq is better than list if use O(n) space
I referred below
@laeshiny But you're not just inserting into the heap. You're also popping from it, which averages O(log n), so the heap solution also averages only O(n log n), not O(n).
@StefanPochmann You're right. I missed calculating popping from it. Thank you for your reply :)
In conclusion, the heap solution also average O(n log n) and it is not better than sorted.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.