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
Python solution beats 99.08% but using O(n) space


@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) spaceI 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.