Sort a linked list in O(n log n) time using constant space complexity.
Difficulty: Medium
思路：对于数组元素排序时间复杂度为O(nlogn)的方式有快速排序，归并排序，堆排序。由于题目要求，空间复杂度为常数阶，考虑使用归并排序来解决。
首先，定义一个快指针和一个慢指针，从链表的头部开始，慢指针一次走一步，快指针一次走两步。当快指针->next = null是 满指针正好在链表中间，此时另满指针->next = null；就将一个链表分成两段。递归该操作。直到每一个链表都只有一个元素。然后再进行根据元素大小依次归并。
例如： 3 -> 1 -> 4 -> 2
第一次： 3 -> 1 -> null 4 -> 2 -> null
第二次： 3 -> null 1-> null 4 -> null 2 -> null
归并返回 ： 1 -> 3 -> null 2 - > 4 -> null
归并返回 : 1 -> 2 -> 3 -> 4 -> null
下面是具体实现源码：
public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // step 1. cut the list to two halves ListNode prev = null, slow = head, fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; // step 2. sort each half ListNode l1 = sortList(head); ListNode l2 = sortList(slow); // step 3. merge l1 and l2 return merge(l1, l2); } ListNode merge(ListNode l1, ListNode l2) { ListNode l = new ListNode(0), p = l; while (l1 != null && l2 != null) { if (l1.val < l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } if (l1 != null) p.next = l1; if (l2 != null) p.next = l2; return l.next; } }
