# Python solution beats 99.08% but using O(n) space

• ``````class Solution(object):
"""
:rtype: ListNode
"""
vals=[]
while h!=None:
vals.append(h.val)
h=h.next`enter code here`
vals.sort()
count=0
while h1!=None:
h1.val=vals[count]
count+=1
h1=h1.next

• Try `for val in vals:` instead of the second `while`.

• Breaking the O(1) space restriction, this problem is trival

• I thinks that it would better to use heapq instead of list like below if use O(n) space

``````        import heapq as hq
h = []
while cursor:
hq.heappush(h, cursor.val)
cursor = cursor.next

while cursor:
cursor.val = hq.heappop(h)
cursor = cursor.next

``````

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