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
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.