最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Java利用递归实现链表的归并排序代码示例
时间:2020-09-14 编辑:袖梨 来源:一聚教程网
本篇文章小编给大家分享一下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; // 将前后链表断开 //... }
cut递归的终止条件 base case 为当head.next == null,即链表只有一个节点。
归并merge环节:
使用辅助指针,将前后链表后合并为一个有序链表
ListNode sortList(ListNode head) { //... // left 为前链表的头节点, right 为后链表的头节点, h 为辅助节点 while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } h.next = left != null ? left : right; //... }
明白上面的两个环节后,就能轻松明白我们完整的算法了。
ListNode sortList(ListNode head) { if (head == null || head.next ==null) return head; // cut过程 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; // merage过程 ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode h = new ListNode(0); ListNode res = h; while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } h.next = left != null ? left : right; return res.next; }
-
上一个: SpringBoot之访问静态资源解析
-
下一个: java token生成和校验的实例代码
相关文章
- SpringBoot自定义bean绑定解析 10-24
- Javaweb工程运行报错HTTP Status 404解决教程 10-20
- JAVA获取jvm和操作系统相关信息方法 10-20
- BeanFactory和FactoryBean的区别讲解 10-20
- 微信小程序的宿主环境实现教程 10-10
- dispatchEvent解决重叠元素响应事件教程 10-10