Java 利用递归实现链表的归并排序
利用归并排序，我们可以将时间复杂度降至O（nlogn),并且我们是对链表进行排序，可以通过修改引用来更改节点顺序，无需像数组一样开辟而外的空间。
利用递归实现链表的归并排序有两个环节：
分割cut环节：
我们可以利用fast,slow快慢双指针实现链表的分割,fast一次移动两位,slow一次移动一位，当fast移动到末尾时，slow移动到中间位置。
利用变量为tmp=slow.next记录后链表的头节点，并将slow.next=null将前后链表断开。
ListNodesortList(ListNodehead){
if(head==null||head.next==null)
returnhead;
ListNodefast=head.next,slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;//一次移动两位
slow=slow.next;//一次移动一位
}
ListNodetmp=slow.next;//记录后链表的头节点
slow.next=null;//将前后链表断开
//...
}
cut递归的终止条件basecase为当head.next==null,即链表只有一个节点。
归并merge环节：
使用辅助指针，将前后链表后合并为一个有序链表
ListNodesortList(ListNodehead){
//...
//left为前链表的头节点，right为后链表的头节点，h为辅助节点
while(left!=null&&right!=null){
if(left.val
明白上面的两个环节后，就能轻松明白我们完整的算法了。
ListNodesortList(ListNodehead){
if(head==null||head.next==null)
returnhead;
//cut过程
ListNodefast=head.next,slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNodetmp=slow.next;
slow.next=null;
//merage过程
ListNodeleft=sortList(head);
ListNoderight=sortList(tmp);
ListNodeh=newListNode(0);
ListNoderes=h;
while(left!=null&&right!=null){
if(left.val
以上就是Java利用递归实现链表的归并排序的详细内容，更多关于Java链表排序的资料请关注毛票票其它相关文章！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。