1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return merge(sortList(head), sortList(slow));
}
public ListNode merge(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0), ptr = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
ptr.next = list1;
list1 = list1.next;
} else {
ptr.next = list2;
list2 = list2.next;
}
ptr = ptr.next;
}
if (list1 != null) {
ptr.next = list1;
} else {
ptr.next = list2;
}
return dummy.next;
}
}
|
就是merge sort.
时间复杂度: O(nlogn)
空间复杂度: O(logn)
