JAVA练习301- 排序链表

题目概览给你链表的头结点head请将其按升序排列并返回排序后的链表。示例 1输入head [4,2,1,3]输出[1,2,3,4]示例 2输入head [-1,5,3,4,0]输出[-1,0,3,4,5]示例 3输入head []输出[]提示链表中节点的数目在范围[0, 5 * 10^4]内-10^5 Node.val 10^5进阶你可以在O(n log n)时间复杂度和常数级空间复杂度下对链表进行排序吗来源148. 排序链表 - 力扣LeetCode解题分析方法快慢指针 归并排序归并排序的时间复杂度是 O(nlogn)该排序的原理是将数组不断进行二分拆分直到单个元素然后从最小的数组两两开始不断合并由于子数组是排好序的因此按照顺序挨个比较大小就可以排序。由于链表没有索引我们可以用快慢指针代替慢指针遍历一个节点快指针遍历两个节点当快指针遍历完成时慢指针刚好到中间节点因此我们可以根据慢节点对链表进行拆分从而进行归并排序。时间复杂度O(nlogn)空间复杂度O(logn)/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode sortList(ListNode head) { if (head null) { return head; } return sort(head, null); } public ListNode sort(ListNode start, ListNode end) { if (start end || start.next end) { start.next null; return start; } ListNode a start, b start; while(b ! end b.next ! end) { a a.next; b b.next.next; } // print(start); ListNode left sort(start, a);; ListNode right sort(a, end); return merge(left, right); } private void print(ListNode a) { StringBuilder sb new StringBuilder(); while(a ! null) { sb.append(a.val); sb.append(,); a a.next; } System.out.println(sb.toString()); } public ListNode merge(ListNode a, ListNode b) { ListNode res new ListNode(), pre res; while(a ! null b ! null) { if (a.val b.val) { pre.next a; a a.next; } else { pre.next b; b b.next; } pre pre.next; } if (a ! null) { pre.next a; } else if (b ! null) { pre.next b; } return res.next; } }