av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術文章
文章詳情頁

Java 利用遞歸實現鏈表的歸并排序

瀏覽:13日期:2022-08-24 17:24:27

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環節:

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

Java 利用遞歸實現鏈表的歸并排序

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 利用遞歸實現鏈表的歸并排序的詳細內容,更多關于Java 鏈表排序的資料請關注好吧啦網其它相關文章!

標簽: Java
相關文章:
主站蜘蛛池模板: 国产伦精品一区二区三毛 | 免费视频一区二区三区在线观看 | 日韩欧美三区 | 新疆少妇videos高潮 | 美女天天干 | 亚洲 精品 综合 精品 自拍 | 精品国产三级 | 在线观看h视频 | 精品1区2区 | 天天综合网7799精品 | 国产日韩欧美一区二区在线播放 | 国产精品美女久久久久aⅴ国产馆 | 久久久久久综合 | 欧美日韩综合精品 | 凹凸日日摸日日碰夜夜 | 中文字幕综合 | 久久久影院 | 亚洲精品亚洲人成人网 | 成人av播放 | 国产在线网址 | 99re在线| 色婷婷综合成人av | 国产精品视频区 | 草久网 | 国产精品国产三级国产播12软件 | 中文字幕免费在线 | 日韩午夜影院 | 精品视频国产 | 亚洲精品一区中文字幕乱码 | 国产精品国产三级国产aⅴ中文 | 九九久久这里只有精品 | 国产一区二区精品在线观看 | 欧美黄 片免费观看 | 国产日韩欧美中文字幕 | 国产sm主人调教女m视频 | 精品国产乱码久久久久久1区2区 | 国产精品黄色 | 一区二区视屏 | 亚洲欧美综合精品久久成人 | 中文字幕av网站 | 成人网视频|