题目：
Sort a linked list in O(n log n) time using constant space complexity.
关键字：链表排序+稳定算法+时间复杂度最低
思路：稳定+算法复杂度的（限定 O(n log n)）只有归并排序
https://blog.csdn.net/u012429555/article/details/89433932
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode mid = getMid(head);
ListNode midNext = mid.next;
mid.next = null;
return mergeSort(sortList(head), sortList(midNext));
}
//求得中间节点
/**
* 获取连接的中间，两个指针，一个走一步，一个走两步，两步走完时，慢指针刚好到了中间的部分
* @param head
* @return
*/
private ListNode getMid(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode slow = head, quick = head;
while(quick.next != null && quick.next.next != null) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
/**
* 合并两个链表
* @param sortList
* @param sortList2
* @return
*/
private ListNode mergeSort(ListNode n1, ListNode n2) {
ListNode preHead = new ListNode(0), cur1 = n1, cur2 = n2, cur = preHead;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
cur.next = cur1 == null ? cur2 : cur1;
return preHead.next;
}
}
