/*
* 148. Sort List
* 11.28 by Mingyang
* 因为题目要求的是nlogn的时间复杂度,所以我们这边只能用merge sort来排序
* 注意,这道题目的时候千万不要按照index来分成两边,必须要两个point一快一慢来进行分类
*/
public static ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode slow = head, fast = head, firsthalf = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondhalf = slow.next;
slow.next = null;
ListNode leftlist = sortList(firsthalf);
ListNode rightlist = sortList(secondhalf);
return mergeTwoLists(leftlist, rightlist);
}