Description
Given the head of a linked list, return the list after sorting it in ascending order**.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:
Input: head = []
Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. 105 <= Node.val <= 105
Solutions
Solution 1
Intuition
This is a good question
- you need to find the mid of list, and split it to two lists
- you need to merge these above lists.
We have a template for merge sort below.
private int[] temp = new int[5_0000];
private void mergeSort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int mid = l + r >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= r) {
temp[k++] = nums[j++];
}
for (i = l, j = 0; i <= r; i++, j++) {
nums[i] = temp[j];
}
}
Code
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode[] halfSplits = split(head);
ListNode l = sortList(halfSplits[0]);
ListNode r = sortList(halfSplits[1]);
return merge(l, r);
}
private ListNode[] split(ListNode head) {
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
prev.next = null;
return new ListNode[] { head, mid };
}
private ListNode merge(ListNode l, ListNode r) {
ListNode dummy = new ListNode();
ListNode head = dummy;
while (l != null && r != null) {
if (l.val < r.val) {
head.next = l;
l = l.next;
} else {
head.next = r;
r = r.next;
}
head = head.next;
}
if (l != null) {
head.next = l;
}
if (r != null) {
head.next = r;
}
return dummy.next;
}
}
Complexity
- Time: O(nlogn)
- Space: O(1)
Top comments (0)