class Solution {
private:
//return last node
ListNode* sortPart(ListNode* first){
if(first>next==NULL)return first;
if(first>next>next==NULL)return first>next;
ListNode* last=first,*pa=first>next,*pa2=pa,*tail=pa,*tmp=NULL;
int p=pa>val;
bool flag=true;
//partition using pa
while(tail>next){
tmp=tail>next;
int t=tmp>val;
if(t<p){
last>next=tmp;
last=last>next;
tail>next=tmp>next;
}else{
//I use pa2 to record the end of the list part begin from pa, where the node's val = pa>val.We don't need to sort this part.
// Actually, I made this operation because my code runs extremely slow(about 1000ms) when the input is a large array consists of 1,2,3. the partition can always be imbalance. It's not a very clean approach, and consequently, my total runtime is 56ms, not good.
if(t!=p)flag=false;
if(flag)pa2=tail;
tail=tail>next;
}
}
last>next=NULL;
//part1:from first to last
last=sortPart(first);
last>next=pa;
//part2:from pa2 to tail
last=sortPart(pa2);
return last;
}
public:
ListNode* sortList(ListNode* head) {
ListNode* first=new ListNode(0);
first>next=head;
ListNode* tail=sortPart(first);
tail>next=NULL;
return first>next;
}
};
C++ Solution using quicksort


@xiongjzh well, anything that uses recursive call is wrong, because it will be using O(n log n) stack space.