Java 利用遞歸實(shí)現(xiàn)鏈表的歸并排序
利用歸并排序，我們可以將時(shí)間復(fù)雜度降至O（nlogn), 并且我們是對(duì)鏈表進(jìn)行排序，可以通過(guò)修改引用來(lái)更改節(jié)點(diǎn)順序，無(wú)需像數(shù)組一樣開辟而外的空間。
利用遞歸實(shí)現(xiàn)鏈表的歸并排序有兩個(gè)環(huán)節(jié)：
分割cut環(huán)節(jié)：
我們可以利用fast, slow快慢雙指針實(shí)現(xiàn)鏈表的分割, fast一次移動(dòng)兩位, slow一次移動(dòng)一位，當(dāng)fast移動(dòng)到末尾時(shí)，slow移動(dòng)到中間位置。
利用變量為tmp = slow.next記錄后鏈表的頭節(jié)點(diǎn)，并將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; // 一次移動(dòng)兩位
slow = slow.next; // 一次移動(dòng)一位
}
ListNode tmp = slow.next; // 記錄后鏈表的頭節(jié)點(diǎn)
slow.next = null; // 將前后鏈表斷開
//...
}
cut遞歸的終止條件 base case 為當(dāng)head.next == null,即鏈表只有一個(gè)節(jié)點(diǎn)。
歸并merge環(huán)節(jié)：
使用輔助指針，將前后鏈表后合并為一個(gè)有序鏈表
ListNode sortList(ListNode head) {
//...
// left 為前鏈表的頭節(jié)點(diǎn)， right 為后鏈表的頭節(jié)點(diǎn)， h 為輔助節(jié)點(diǎn)
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;
//...
}
明白上面的兩個(gè)環(huán)節(jié)后，就能輕松明白我們完整的算法了。
ListNode sortList(ListNode head) {
if (head == null || head.next ==null)
return head;
// cut過(guò)程
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過(guò)程
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 利用遞歸實(shí)現(xiàn)鏈表的歸并排序的詳細(xì)內(nèi)容，更多關(guān)于Java 鏈表排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
spring+maven實(shí)現(xiàn)發(fā)送郵件功能
這篇文章主要為大家詳細(xì)介紹了spring+maven實(shí)現(xiàn)發(fā)送郵件功能，利用spring提供的郵件工具來(lái)發(fā)送郵件，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-07-07
JetBrains?產(chǎn)品輸入激活碼?Key?is?invalid?完美解決方案
JetBrains?系列產(chǎn)品（IDEA、Pycharm?等）使用本站破解教程?(opens?new?window)，在輸入激活碼時(shí)，部分小伙伴反應(yīng)說(shuō)提示?Key?is?invalid?無(wú)法激活，今天小編給大家分享完美解決方案，感興趣的朋友跟隨小編一起看看吧2022-11-11
Lombok是一款Java開發(fā)插件，使得Java開發(fā)者可以通過(guò)其定義的一些注解來(lái)消除業(yè)務(wù)工程中冗長(zhǎng)和繁瑣的代碼，它能夠在編譯源代碼期間自動(dòng)幫我們生成這些方法，并沒(méi)有如反射那樣降低程序的性能。下面我們來(lái)詳細(xì)了解一下吧2019-06-06
struts升級(jí)到2.5.2遇到的問(wèn)題及解決方案(推薦)
原來(lái)的版本是2.3.x，由于安全原因需要升級(jí)到2.5.2。但是在升級(jí)過(guò)程中遇到各種各樣的問(wèn)題，下面小編給大家?guī)?lái)了struts升級(jí)到2.5.2遇到的問(wèn)題及解決方案，需要的朋友參考下吧2016-11-11
在程序設(shè)計(jì)中，我們有時(shí)可能希望某些數(shù)據(jù)是不能夠改變的，這個(gè)時(shí)候final就有用武之地了。final是java的關(guān)鍵字，本文就詳細(xì)說(shuō)明一下他的使用方法2013-11-11
Java在長(zhǎng)字符串中查找短字符串的實(shí)現(xiàn)多種方法
這篇文章主要介紹了Java在長(zhǎng)字符串中查找短字符串的實(shí)現(xiàn)多種方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
基于Javamail實(shí)現(xiàn)發(fā)送郵件(QQ/網(wǎng)易郵件服務(wù)器)
這篇文章主要介紹了基于Javamail實(shí)現(xiàn)發(fā)送郵件，分別使用QQ郵箱作為smtp郵件服務(wù)器發(fā)送郵件，使用網(wǎng)易郵箱作為smtp郵件服務(wù)器發(fā)送郵件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-08-08
Spring實(shí)戰(zhàn)之Qualifier注解用法示例
這篇文章主要介紹了Spring實(shí)戰(zhàn)之Qualifier注解用法,結(jié)合實(shí)例形式詳細(xì)分析了spring Qualifier注解相關(guān)配置、定義與使用方法,需要的朋友可以參考下2019-12-12
在本篇文章里小編給大家整理的是一篇關(guān)于java Wrapper類基本用法詳解，有興趣的朋友們可以參考下。2021-01-01
spring boot前后端傳參的實(shí)現(xiàn)
這篇文章主要介紹了spring boot前后端傳參的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-01-01