Question
Given the head of a linked list, return the list after sorting it in ascending order.
https://leetcode.com/problems/sort-list/
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
36
37
| class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode mid = findMid(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
private ListNode findMid(ListNode head){
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode head1, ListNode head2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (head1 != null && head2 != null){
if (head1.val < head2.val){
cur.next = head1;
head1 = head1.next;
} else{
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
if (head1 == null) cur.next = head2;
else cur.next = head1;
return dummy.next;
}
}
|
Complexity:
Time complexity: O( nlogn)
Space complexity: O(logn)