溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關Java 利用遞歸實現鏈表歸并排序的方法，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
利用歸并排序，我們可以將時間復雜度降至O（nlogn), 并且我們是對鏈表進行排序，可以通過修改引用來更改節點順序，無需像數組一樣開辟而外的空間。
利用遞歸實現鏈表的歸并排序有兩個環節：
分割cut環節：
我們可以利用fast, slow快慢雙指針實現鏈表的分割, fast一次移動兩位, slow一次移動一位，當fast移動到末尾時，slow移動到中間位置。
利用變量為tmp = slow.next記錄后鏈表的頭節點，并將slow.next = null將前后鏈表斷開。
ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next; // 一次移動兩位
slow = slow.next; // 一次移動一位
}
ListNode tmp = slow.next; // 記錄后鏈表的頭節點
slow.next = null; // 將前后鏈表斷開
//...
}cut遞歸的終止條件 base case 為當head.next == null,即鏈表只有一個節點。
歸并merge環節：
使用輔助指針，將前后鏈表后合并為一個有序鏈表
ListNode sortList(ListNode head) {
//...
// left 為前鏈表的頭節點， right 為后鏈表的頭節點， h 為輔助節點
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
//...
}明白上面的兩個環節后，就能輕松明白我們完整的算法了。
ListNode sortList(ListNode head) {
if (head == null || head.next ==null)
return head;
// cut過程
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode tmp = slow.next;
slow.next = null;
// merage過程
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}以上就是Java 利用遞歸實現鏈表歸并排序的方法，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
