中等难度，但是需要用到divide & conquer的思想，个人感觉还是比较有难度，题目描述如下：
Sort a linked list in O(n log n) time using constant space complexity.
要求时间复杂度为O(n log n)空间复杂度为O(1)，分析可知，只能用分治的思想来完成才能达到要求，因为只有分治，每次处理一个partition才会是常数空间。 排序的方法是mergesort,mergesort的步骤一般分为分段（partition）与合并（merge），代码如下：
public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode f = head.next.next; ListNode p = head; //这样的移动方法可以将p移动到list中心，是list移动到中心的常用方法 while (f != null && f.next != null) { p = p.next; f = f.next.next; } //h2代表每个已排序部分的头指针 ListNode h2 = sortList(p.next); //这里每次选择p->next迭代是非常有必要的，因为链表不能访问前一个元素，每次迭代完成后p都恰好代表已排序链表的**前一个元素**，通过p->next=NULL可以达到断链的作用 p.next = null; return merge(sortList(head), h2); } //归并部分，通过对两部分已经排序过的数列进行比较进行归并 public ListNode merge(ListNode h1, ListNode h2) { ListNode newHead = new ListNode(Integer.MIN_VALUE); ListNode c = hn; while (h1 != null && h2 != null) { if (h1.val < h2.val) { c.next = h1; h1 = h1.next; } else { c.next = h2; h2 = h2.next; } c = c.next; } //剩下的数字都是比较大的数字，直接连接起来就好了 pt->next=h1?h1:h2; return newHead.next; } }以5-1-4-3-2->NULL的链表为例，排序的过程是(从后往前)：
1. 5 1 4 2 3 (merge (2)(3)) 2. 5 1 2 3 4 (merge (4)(2 3))//h2=sortList(head); 3. 1 5 2 3 4(merge(1) (5))//return merge(sortList(head), h2)中的sortList(head) 4. 1 2 3 4 5(merge(1 5)(2 3 4))//return merge(sortList(head), h2)