I tried to implement by recursion with O(nlogn). but got exceed time limit error.
I've tried to compare the head node with a sorted list, so it will take O(N), with recursion, it will take O(nlogn).
/* class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}
*/
public class Solution {
public ListNode sortList(ListNode head) {
if(head==null) return null;ListNode first = head;
ListNode current = head;
ListNode next = current.next;if(next==null) return first;
next = sortList(current.next);
while(next!=null){ //here it will insert the current node into sorted list, so O(N)
if(current.val>next.val){
ListNode tempnode = next.next;
current.next = tempnode;
next.next = current;
}
next = next.next;
}
return first;
}
}