帶註釋：
核心思想，歸併排序
時間複雜度O（nlogn）
空間複雜度O（n）
/** * Definition for singly-linked list。 * public class ListNode { * int val； * ListNode next； * ListNode（） {} * ListNode（int val） { this。val = val； } * ListNode（int val， ListNode next） { this。val = val； this。next = next； } * } */class Solution { public ListNode sortList（ListNode head） { //nullcheck if（head == null || head。next == null）{ return head； } return mergeSort（head）；//歸併方法 } private ListNode mergeSort（ListNode head）{ //nullcheck if（head == null || head。next == null）{ return head； } //快慢指標找出中間位置，有了中間位置就可以把連結串列分為左右連結串列 ListNode slow = head， fast = head， pre =null； while（fast ！= null && fast。next ！= null）{ pre = slow； fast = fast。next。next； slow = slow。next； } //到尾巴了 pre。next = null；//連結串列結束 ListNode left = mergeSort（head）；//左邊進行排序，區間（head 到mid = slow）位置 ListNode right = mergeSort（slow）；//後邊進行排序，連結串列是slow開始，陣列的是區間（mid+1，fast）位置 return merge（left，right）；//排序好了，再並，呼叫合併方法 } //核心，如何合併 private ListNode merge（ListNode left， ListNode right）{ ListNode tempHead = new ListNode（0）；//輔助頭節點，用來存放排序合併的值， ListNode cur = tempHead；//指標指向頭節點 while（left ！= null && right ！= null）{ if（left。val <= right。val）{ cur。next = left；//比較左右倆連結串列的值，一個個比較，往後遍歷，小的複製到temp連結串列 cur = cur。next；//輔助陣列指標後移 left = left。next；//後移 }else{ cur。next = right；//比較左右倆連結串列的值，一個個比較，往後遍歷，小的複製到temp連結串列 cur = cur。next；//輔助陣列指標後移 right = right。next；//後移 } //迴圈退出條件是倆個連結串列都遍歷完了 //cur = cur。next；這個語句可以寫這裡 } //如果有一方先結束遍歷了，另一個就直接賦值給temp if（left ！= null）{ cur。next = left； } if（right ！= null）{ cur。next = right； } return tempHead。next；// } }
歸併和快排的方法都要掌握
晚上更新快排解法：P
