Java利用遞歸實(shí)現(xiàn)鏈表歸并排序的方法-創(chuàng)新互聯(lián)
本篇文章給大家分享的是有關(guān)Java 利用遞歸實(shí)現(xiàn)鏈表歸并排序的方法，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
利用歸并排序，我們可以將時(shí)間復(fù)雜度降至O（nlogn), 并且我們是對鏈表進(jìn)行排序，可以通過修改引用來更改節(jié)點(diǎn)順序，無需像數(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; // 將前后鏈表斷開
//...
} 文章標(biāo)題：Java利用遞歸實(shí)現(xiàn)鏈表歸并排序的方法-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://m.jiaotiyi.com/article/jpiop.html