欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java 利用递归实现链表的归并排序

程序员文章站 2022-06-15 13:01:23
利用归并排序,我们可以将时间复杂度降至o(nlogn), 并且我们是对链表进行排序,可以通过修改引用来更改节点顺序,无需像数组一样开辟而外的空间。利用递归实现链表的归并排序有两个环节:分割cut环节:...

Java 利用递归实现链表的归并排序

利用归并排序,我们可以将时间复杂度降至o(nlogn), 并且我们是对链表进行排序,可以通过修改引用来更改节点顺序,无需像数组一样开辟而外的空间。

利用递归实现链表的归并排序有两个环节:

分割cut环节:

我们可以利用fast, slow快慢双指针实现链表的分割, fast一次移动两位, slow一次移动一位,当fast移动到末尾时,slow移动到中间位置。

利用变量为tmp = slow.next记录后链表的头节点,并将slow.next = null将前后链表断开。

cut递归的终止条件 base case 为当head.next == null,即链表只有一个节点。

归并merge环节:

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

Java 利用递归实现链表的归并排序

明白上面的两个环节后,就能轻松明白我们完整的算法了。

以上就是java 利用递归实现链表的归并排序的详细内容,更多关于java 链表排序的资料请关注其它相关文章!