Merge Sort 的 Linked List 实现版本。
对于 Array 来说，Merge Sort 的 Time Complexity 为 O(n + nlogn) = O(nlogn)，这其中的O(n) 是大问题到小问题拆分的时间（第一层1+第二层2+…+第n层n） O(nlogn) 是 merge 需要的总时间（每一层需要 O(n) 时间 * recursion stack 层数 O(logn)）； Space Complexity 为 O(n + logn) = O(n)，这其中的 O(n) 是谁小移谁需要的额外空间，O(logn) 是 recursion stack 的空间。
对于 Linked List 来说，Merge Sort 的 Time Complexity 为 O(nlogn + nlogn) = O(nlogn)；Space Complexity 为 O(logn)。（所以本题要求 using constant space complexity，这个做法其实是不合适的。Constant space complexity 的解法今后再补。）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMid(head);
ListNode left = head;
ListNode right = mid.next;
mid.next = null;
return merge(sortList(left), sortList(right));
}
private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
cur.next = new ListNode(left.val);
cur = cur.next;
left = left.next;
} else {
cur.next = new ListNode(right.val);
cur = cur.next;
right = right.next;
}
}
if (left != null) {
cur.next = left;
}
if (right != null) {
cur.next = right;
}
return dummy.next;
}
}