排序链表
2021-06-04 21:04
标签：loading slow nlogn 代码 blank next rtl ext node 给定链表的头结点head，返回排序后的链表，按照由小到大的顺序。 归并排序时间复杂度是O(nlogn) 排序链表 标签：loading slow nlogn 代码 blank next rtl ext node 原文地址：https://www.cnblogs.com/dataoblogs/p/14639671.htmlLeetCode148 排序链表
题目
输入：head = [4,2,1,3]
输出：[1,2,3,4]分析
代码实现
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
//定义快慢指针
ListNode fast = head.next, slow = head;
//找出中间节点位置
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
//将链表一分为二
slow.next = null;
//递归分解链表
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode listNode = new ListNode(0);
ListNode res = listNode;
//合并左边部分和右边部分
while (left!=null&&right!=null){
if (left.val
空间复杂度是O(n)
下一篇：java类加载器有哪些？