# java use quick sort to sort the list, beats 93.21%

• like the method of three pointers. Maybe not very short,but the thought is quite clear and easily understood.

``````public class Solution {
public ListNode sortList(ListNode head) {
}
ListNode mid = getMid(head);
int midval= mid.val;
ListNode leftdummy=new ListNode(0),middummy=new ListNode(0),rightdummy=new ListNode(0);
ListNode leftwork=leftdummy,midwork=middummy,rightwork=rightdummy;
while(work!=null){
if(work.val<midval){
leftwork.next=work;
leftwork=work;
}
else if(work.val==midval){
midwork.next=work;
midwork=work;
}
else{
rightwork.next=work;
rightwork=work;
}
work=work.next;
}
leftwork.next=null;  midwork.next=null;  rightwork.next=null;
ListNode left= sortList(leftdummy.next);
ListNode right = sortList (rightdummy.next);
return connectAll(left,middummy.next,right);

}
public ListNode connectAll(ListNode l1,ListNode l2,ListNode l3){
ListNode dummy= new ListNode (0);
ListNode work=dummy;
if(l1!=null){
work.next=l1;
work=tail(l1);
}
if(l2!=null){
work.next=l2;
work=tail(l2);
}
if(l3!=null){
work.next=l3;
}
return dummy.next;
}

public ListNode tail (ListNode l){
ListNode work=l;
while(work.next!=null){
work=work.next;
}
return work;
}

public ListNode getMid(ListNode head){
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
}
return slow;
}
}
``````

• @KnightRider Recursive, not really constant space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.