```
class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
#constant space
if head is None:
return
copy = []
pr = head
#O(n)
while pr is not None:
copy.append((pr.val, pr))
pr = pr.next
# copy contains val and address of one node
copy = sorted(copy)#O(nlgn) time can use quick sort
for i in range(len(copy)-1):
_, adr = copy[i]
adr.next = copy[i+1][1]
copy[-1][1].next = None
head = copy[0][1]
return head
```