题目给你链表的头结点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 * 104]内-105 Node.val 105进阶你可以在O(n log n)时间复杂度和常数级空间复杂度下对链表进行排序吗题解/** * 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 || head.next null){ return head; } // 快慢指针找中点 ListNode slow head, fast head.next; while(fast ! null fast.next ! null){ slow slow.next; fast fast.next.next; } ListNode mid slow.next; slow.next null; // 切断链表分成前后两段 ListNode left sortList(head); ListNode right sortList(mid); //合并 return merge(left, right); } // 合并两个有序链表 private ListNode merge(ListNode l1, ListNode l2){ ListNode dummy new ListNode(-1); ListNode cur dummy; while(l1 ! null l2 ! null){ if(l1.val l2.val){ cur.next l1; l1 l1.next; }else{ cur.next l2; l2 l2.next; } cur cur.next; } cur.next l1 ! null ? l1 : l2; return dummy.next; } }思路递归归并快慢指针找链表中点分割成左右两段递归分别排序左、右合并两个有序链表