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; } }