Java 利用遞歸實現(xiàn)鏈表歸并排序的方法

發(fā)布時間：2020-11-03 18:40:22 來源：億速云閱讀：194 作者：Leah 欄目：開發(fā)技術(shù)

本篇文章給大家分享的是有關(guān)Java 利用遞歸實現(xiàn)鏈表歸并排序的方法，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

利用歸并排序，我們可以將時間復雜度降至O（nlogn), 并且我們是對鏈表進行排序，可以通過修改引用來更改節(jié)點順序，無需像數(shù)組一樣開辟而外的空間。

利用遞歸實現(xiàn)鏈表的歸并排序有兩個環(huán)節(jié)：

分割cut環(huán)節(jié)：

我們可以利用fast, slow快慢雙指針實現(xiàn)鏈表的分割, fast一次移動兩位, slow一次移動一位，當fast移動到末尾時，slow移動到中間位置。

利用變量為tmp = slow.next記錄后鏈表的頭節(jié)點，并將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; // 記錄后鏈表的頭節(jié)點
 slow.next = null; // 將前后鏈表斷開
 //...
}

cut遞歸的終止條件 base case 為當head.next == null,即鏈表只有一個節(jié)點。

歸并merge環(huán)節(jié)：

使用輔助指針，將前后鏈表后合并為一個有序鏈表

Java 利用遞歸實現(xiàn)鏈表歸并排序的方法

ListNode sortList(ListNode head) {
 //...
 // left 為前鏈表的頭節(jié)點， right 為后鏈表的頭節(jié)點， h 為輔助節(jié)點
 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 &#63; left : right;
 //...
}

明白上面的兩個環(huán)節(jié)后，就能輕松明白我們完整的算法了。

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 &#63; left : right;

    return res.next;
  }

以上就是Java 利用遞歸實現(xiàn)鏈表歸并排序的方法，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。

向AI問一下細節(jié)

Java 利用遞歸實現(xiàn)鏈表歸并排序的方法

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽