Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
解法一：堆排序
考虑如果被排序对象不是链表的节点，而是普通数字的情况下，此题可以用块排，堆排序等搞定。考虑到链表结构的复杂性，可以选用堆排序。将每个节点依次送入堆中，然后再从堆顶依次输出并连接成新链表即可。代码如下：
public static ListNode sortList(ListNode head) {Queue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {@Overridepublic int compare(ListNode node1, ListNode node2) {if(node1.val > node2.val) {return 1 ;} else if (node1.val == node2.val) {return 0 ;} else {return -1 ;}}}) ;while(head != null) {heap.offer(head) ;head = head.next ;}ListNode p = heap.poll() ;head = p ;while(!heap.isEmpty()) {p.next = heap.poll() ;p = p.next ;}return head ;}
解法二：基于二路归并
解法一虽然简单但是不满足空间复杂度是常量范围内的要求。究其原因，是因为上面的代码重新开辟了一片空间用于存放堆内的数据。但是这个堆的大小是随链表的长度变化而变化的。所以要想符合空间复杂度O(1)的要求，目前只能考虑在原地交换链表节点，而不是生成新的链表节点，所以堆排序就不太好搞了。于是我们可以考虑使用归并排序。注意merge两个链表时不要创建任何临时节点，否则依然不符合空间复杂度要求。代码如下：
public static ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode p = head ;while(p.next != null) {p = p.next ;}ListNode mid = getMiddleNode(head) ;ListNode leftHead = head ;ListNode rightHead = mid.next ;mid.next = null ;ListNode left = sortList(leftHead) ;ListNode right = sortList(rightHead) ;return merge(left, right) ;}private static ListNode merge(ListNode left, ListNode right) {ListNode head = null ;ListNode root = null ;while(left != null && right != null) {if(left.val < right.val) {if(head == null) {head = left ;root = left ;} else {head.next = left ;head = head.next ;}left = left.next ;head.next = null ;} else {if(head == null) {head = right ;root = right ;} else {head.next = right ;head = head.next ;}right = right.next ;head.next = null ;}}if(left != null) {head.next = left ;}if(right != null) {head.next = right ;}return root ;}private static ListNode getMiddleNode(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;}