# What's the problem with my C++ Quick Sort? Why time out?

• ``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *sortList(ListNode *head) {
}

ListNode* tail = head;
while(tail->next != NULL){
tail = tail->next;
}

}

ListNode *_sortList(ListNode* &head, ListNode* &tail){
}

//fake headers for appending
ListNode* small = new ListNode(0);
ListNode* small_t = small;
ListNode* big = new ListNode(0);
ListNode* big_t = big;

//devide
for(ListNode* p = head->next; p != NULL;){
ListNode* tmp = p;
p = p->next;
small_t->next = tmp;
small_t = tmp;
tmp->next = NULL;
}
else{
big_t->next = tmp;
big_t = tmp;
tmp->next = NULL;
}
}

//sort each side
_sortList(big->next, big_t);
_sortList(small->next, small_t);

if(big_t != big){
tail = big_t;
}
else{
}

delete big;
if(small->next != NULL){
}
delete small;

}
};``````

• `````` while(tail->next != NULL){
tail = tail->next;
}
``````

No need find the tail. Just use null as the tail.

• Quicksort is O(n^2) btw

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