Merge sort O(nlogn)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode mid = findMiddle(head);
ListNode l1 = head;
ListNode l2 = mid.next;
mid.next = null;
l1 = sortList(l1);
l2 = sortList(l2);
// merge 2 lists
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1!=null && l2!=null){
if (l1.val<l2.val) {cur.next = l1; l1 = l1.next;}
else {cur.next = l2; l2 = l2.next;}
cur = cur.next;
}
if (l1!=null) cur.next = l1;
else cur.next = l2;
return dummy.next;
}
public ListNode findMiddle(ListNode head){
ListNode slow = head, fast = head;
while (fast.next!=null && fast.next.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}