本篇文章给大家分享的是有关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 利用递归实现链表归并排序的方法，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
