Sort a linked list in O(n log n) time using constant space complexity.
这里采用merge sort。每次把linked list用slow和fast分成两段，再进行merge。代码如下：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode prev = head, slow = head, fast = head; while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } prev.next = null; ListNode l1 = sortList(head); ListNode l2 = sortList(slow); return merge(l1, l2); } private ListNode merge(ListNode l1, ListNode l2) { ListNode l = new ListNode(0); ListNode 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 = l2; } if (l2 == null) { p.next = l1; } return l.next; } }