大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇文章给大家分享的是有关Java 利用递归实现链表归并排序的方法,小编觉得挺实用的,因此分享给大家学习,希望大家阅读完这篇文章后可以有所收获,话不多说,跟着小编一起来看看吧。
成都创新互联是一家专注于做网站、成都网站建设与策划设计,右玉网站建设哪家好?成都创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:右玉等地区。右玉做网站价格咨询:13518219792利用归并排序,我们可以将时间复杂度降至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; // 将前后链表断开 //... }