一.題目描述
給你連結清單的頭結點 head ，請将其按 升序 排列并傳回 排序後的連結清單 。
進階：
你可以在 O(n log n) 時間複雜度和常數級空間複雜度下，對連結清單進行排序嗎？
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
輸入：head = []
輸出：[]
提示：
連結清單中節點的數目在範圍 [0, 5 * 104] 内
-105 <= Node.val <= 105
二.題目解析
public ListNode sortList1(ListNode head) {
/*暴力法.時間複雜度O(nlogn),空間複雜度O(n)
* */
ListNode cur = head;
int count = 0,i;
//第一次周遊獲得所有的節點數
while (cur != null){
count++;
cur = cur.next;
}
//第二次周遊把節點值存儲在數組裡
int[] arr = new int[count];
for (cur = head,i = 0; i < count; i++,cur = cur.next) {
arr[i] = cur.val;
}
//對數組進行排序
Arrays.sort(arr);
//第三次周遊更新連結清單的值
for (cur = head,i = 0; i < count; i++,cur = cur.next) {
cur.val = arr[i];
}
return head;
}
2.根據時間複雜度想到二分法，進而聯想到歸并排序
分：把原連結清單分為兩個子連結清單的歸并排序
治：在切割後的子連結清單隻要滿足節點個數大于1的時候就一直分；
合：合并切割後的子連結清單為有序連結清單，依次向上合并
對數組做歸并排序的空間複雜度為 O(n)，分别由merge部分新開辟數組O(n)和遞歸函數調用O(logn)組成，
根據連結清單特性：
數組額外空間：連結清單可以通過修改引用來更改節點順序，無需像數組一樣開辟額外空間；
遞歸額外空間：遞歸調用函數将帶來O(logn)的空間複雜度，是以若希望達到O(1)空間複雜度，則隻能使用疊代法；
使用遞歸實作自頂向下的歸并排序：
public ListNode sortList(ListNode head) {
/*歸并排序-遞歸法.時間複雜度O(nlogn),空間複雜度O(logn)
* */
//連結清單隻有一個節點需要歸并排序，那麼直接傳回即可
if(head == null || head.next == null){
return head;
}
///分環節，隻要滿足大于1個節點就一直分
//快慢指針法定位連結清單中點（奇數個的話slow正好定位到中點，偶數個的話定位到中點的左邊那個節點）
ListNode fast = head.next,slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
//newHead指向“分”後的第二個連結清單頭結點
ListNode newHead = slow.next;
//斷鍊，實作“分”
slow.next = null;
//before指向前半部分歸并排序之後的連結清單頭結點
ListNode before = sortList(head);
//after指向後半部分歸并排序之後的連結清單頭結點
ListNode after = sortList(newHead);
///merge環節
//将兩個排序連結清單merge，轉化為一個排序連結清單
//建立虛拟頭結點
ListNode dummyHead = new ListNode(-1,null);
//cur指向新連結清單的最後一個節點（merge的過程中持續更新）
ListNode cur = dummyHead;
//如果兩個連結清單都沒到結尾
while (before != null && after != null){
if(before.val <= after.val){
cur.next = before;
before = before.next;
}else{
cur.next = after;
after = after.next;
}
cur = cur.next;
}
//最後隻需要接上較長的那個連結清單剩餘部分即可
cur.next = before == null ? after : before;
return dummyHead.next;
}
3.我們可以使用疊代來代替遞歸，實作自底向上的歸并排序：
public ListNode sortList2(ListNode head) {
/*歸并排序-疊代法.時間複雜度O(nlogn),空間複雜度O(1)
* */
int length = getLength(head);
ListNode dummy = new ListNode(-1);
dummy.next = head;
for(int step = 1; step < length; step*=2){ //每次要merge的兩個連結清單元素個數依次是1,2,4...
//每次變換步長，pre指針和cur指針都初始化在連結清單頭
ListNode pre = dummy;
ListNode cur = dummy.next;
//cur為未處理連結清單的頭結點，while循環不斷把連結清單按照step往下分割，merge，直到待處理連結清單節點是null
while(cur!=null){
//每次循環處理step*2個節點
ListNode h1 = cur; //第一部分頭指向上輪merge後剩餘待處理連結清單的頭結點
ListNode h2 = split(h1,step); //斷鍊後的第二部分頭
//至此原連結清單被分為merge連結清單h1,merge連結清單h2,剩餘連結清單cur
cur = split(h2,step);
//h1（節點個數step個）,h2（節點個數step個）兩兩merge
//temp指向這兩個連結清單merge後的頭結點
ListNode temp = merge(h1,h2);
//将前面merge好的的部分 與 此次merge的兩個連結清單連接配接。此時原連結清單被分為已完成merge的連結清單，未處理的連結清單
pre.next = temp;
//pre指針指向已完成merge的最後一個節點（友善連接配接下輪merge的頭結點）
while(pre.next!=null){
pre = pre.next;
}
}
}
return dummy.next;
}
public int getLength(ListNode head){
//擷取連結清單長度
int count = 0;
while(head!=null){
count++;
head=head.next;
}
return count;
}
public ListNode split(ListNode head,int step){
//斷鍊操作（從head開始計算step個節點後，開始斷鍊）， 傳回第二部分連結清單頭
if(head==null) return null;
ListNode cur = head;
for(int i=1; i<step && cur.next!=null; i++){
cur = cur.next;
}
ListNode right = cur.next;
cur.next = null; //切斷連接配接
return right;
}
public ListNode merge(ListNode h1, ListNode h2){
//合并兩個有序連結清單
ListNode head = new ListNode(-1);
ListNode p = head;
while(h1!=null && h2!=null){
if(h1.val < h2.val){
p.next = h1;
h1 = h1.next;
}
else{
p.next = h2;
h2 = h2.next;
}
p = p.next;
}
if(h1!=null) p.next = h1;
if(h2!=null) p.next = h2;
return head.next;
}