扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
本篇文章给大家分享的是有关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; // 将前后链表断开
//...
} 
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网