import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode insertionSortList (ListNode head) {
// write code here
if (null == head.next) {
return head;
}
int len = 0; // 定义一个整型变量,用于存放链表的长度
ListNode node = head;
while (null != node) {
len++;
node = node.next;
}
int[] arr = new int[len];
int index = 0;
node = head;
while (null != node) {
arr[index] = node.val;
index++;
node = node.next;
}
quickSort(arr, 0, arr.length - 1);
node = head;
for (int num : arr) {
node.val = num;
node = node.next;
}
return head;
}
public void quickSort(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int l = start - 1;
int r = end + 1;
int p = start;
int val = arr[end];
while (p < r) {
if (arr[p] < val) {
int swap = arr[p];
arr[p] = arr[l + 1];
arr[l + 1] = swap;
l++;
p++;
}
else if (arr[p] > val) {
int swap = arr[p];
arr[p] = arr[r - 1];
arr[r - 1] = swap;
r--;
}
else {
p++;
}
}
quickSort(arr, start, l);
quickSort(arr, r, end);
}
}