Java利用递归实现链表归并排序的方法-创新互联

本篇文章给大家分享的是有关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; // 将前后链表断开
 //...
}