The idea is to use O(n) to convert between linked list and array. Then use system-sort, which I assume is O(n lg n). Since I have not create any new node, I think it is O(1) space (or whatever it takes for the system-sort). Is my solution cheating?

```
class Solution:
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
nodes = []
while head:
node = head
head = head.next
node.next = None
nodes.append(node)
nodes.sort(key=lambda n: n.val)
while nodes:
node = nodes.pop()
node.next = head
head = node
return head
```