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环节：

使用辅助指针，将前后链表后合并为一个有序链表

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 链表排序的资料请关注好吧啦网其它相关文章！