/*
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
/
class Solution {
public ListNode quickSortList(ListNode head) {
if(head == null){
return head;
}
quickSort(head,null);
return head;
}
public static void quickSort(ListNode left,ListNode right){
if(left != right){
int k = left.val;
ListNode p = left;
ListNode q = left.next;
while(q != right){
if(q.val < k){
p = p.next;
int num = p.val;
p.val = q.val;
q.val = num;
}
q = q.next;
}
if(p != right){
int num = p.val;
p.val = k;
left.val = num;
}
quickSort(left,p);
quickSort(p.next,right);
}
}
}