利用歸并排序，我們可以將時(shí)間復(fù)雜度降至O（nlogn), 并且我們是對(duì)鏈表進(jìn)行排序，可以通過(guò)修改引用來(lái)更改節(jié)點(diǎn)順序，無(wú)需像數(shù)組一樣開(kāi)辟而外的空間。

利用遞歸實(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將前后鏈表斷開(kāi)。

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; // 將前后鏈表斷開(kāi) //...}

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)注好吧啦網(wǎng)其它相關(guān)文章！