给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

 

 

输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：

 

 

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public ListNode sortList(ListNode head) {
13         // 自顶向下归并排序
14         return sortList(head,null);
15     }
16     // 对[head,tail)进行排序，注意，左闭右开
17     public ListNode sortList(ListNode head, ListNode tail){
18         if (head == null){
19             return head;
20         }
21         // 由于左闭右开，所以是单个节点
22         if(head.next == tail){
23             head.next = null;
24             return head;
25         }
26         // 通过快慢指针，找到中间节点
27         ListNode slow = head;
28         ListNode fast = head;
29         while(fast != tail){
30             slow = slow.next;
31             fast = fast.next;
32             if(fast!= tail){
33                 fast = fast.next;
34             }
35         }
36         ListNode mid = slow;
37         // 以mid分成两个部分进行排序
38         ListNode head1 = sortList(head,mid);
39         ListNode head2 = sortList(mid,tail);
40         return merge(head1,head2);
41     }
42     // 对两条有序链表进行合并
43     public ListNode merge(ListNode head1,ListNode head2){
44         // 新建一个头节点
45         ListNode head = new ListNode(-1);
46         ListNode tmpHead1 = head1;
47         ListNode tmpHead2 = head2;
48         // 声明头节点，用来排序
49         ListNode tmp = head;
50         while (tmpHead1 != null && tmpHead2 != null){
51             if (tmpHead1.val < tmpHead2.val){
52                 tmp.next = tmpHead1;
53                 tmpHead1 = tmpHead1.next;
54             }else{
55                 tmp.next = tmpHead2;
56                 tmpHead2 = tmpHead2.next;
57             }
58             tmp = tmp.next;
59         }
60         // 处理小尾巴
61         if (tmpHead1!= null){
62             tmp.next = tmpHead1;
63         }else{
64             tmp.next = tmpHead2;
65         }
66         return head.next;
67     }
68 }

 

解题关键：

自顶向下归并排序