# I think the complexity of my method is O(NlogN), why still gets a TLE?

• My method is similar to quicksort, and its space complexity is not strictly const. But I think the time complexity is O(nlogn), why still gets a TLE?

``````class Solution {
public:
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.

pair<ListNode*, ListNode*> ret = partition(head, NULL);
return ret.first;
}

pair<ListNode*, ListNode*> partition(ListNode *begin, ListNode *end) {
// return the first and last point of the sorted range [begin, end)
if (begin == NULL || begin->next == end)
return make_pair(begin, begin);

ListNode *p1 = new ListNode(0);
ListNode *first_part = p1;
ListNode *p2 = new ListNode(0);
ListNode *second_part = p2;
int base_val = begin->val;
ListNode *cur = begin->next;
// partition: first_part is the element less than base_val, second_part is the other
while (cur != end) {
if (cur->val < base_val) {
first_part->next = cur;
first_part = cur;
} else {
second_part->next = cur;
second_part = cur;
}
cur = cur->next;
}
first_part->next = NULL;
second_part->next = NULL;

pair<ListNode*, ListNode*> first_pair = partition(p1->next, NULL);
pair<ListNode*, ListNode*> second_pair = partition(p2->next, NULL);
delete p1;
delete p2;
// concatenate
} else {
first_pair.second->next = begin;
}
begin->next = second_pair.first;
if (second_pair.second != NULL)
else

}
};``````

• A simple Quicksort has worst case runtime O(N^2) when you don't carefully choose your pivot.

The following partition would do the trick (but it won't improve the worst case)

``````    while (cur != end) {
if (cur->val < base_val || cur->val == base_val && rand() % 2) {
first_part->next = cur;
first_part = cur;
} else {
second_part->next = cur;
second_part = cur;
}
cur = cur->next;
}
``````

And I agree that this solution does not meet the constant space requirement because you are using recursion.

• Thanks a lot! Now I know what's wrong with my solution.I will try to sovle it using merge sort.

• Try to use a merge sort without recursion =)

• I have an idea, but I need to disconnect the nodes in the original linked list and keep them(the references) in a queue. And try to use the bottom up merge sort the sort the linked list like you said. But it's time limit exceeded. Could you have a look at my code, I'm appreciated for your help.

``````public class Solution {

ArrayList<ListNode> Q = new ArrayList<ListNode>();

}

while (Q.size()>1) {
ListNode a = Q.remove(0);
ListNode b = Q.remove(0);
ListNode t = combineLists(a, b);
}
return (Q.remove(0));
}

public ListNode combineLists(ListNode l1, ListNode l2) {
ListNode end;

if (l1 == null) return l2;
else if (l2 == null) return l1;

if (l1.val<l2.val) {
end = l1;
l1 = l1.next;
} else {
end = l2;
l2 = l2.next;
}

while (l1 != null && l2 != null) {
if (l1.val<l2.val) {
end.next = l1;
end = l1;
l1 = l1.next;
} else {
end.next = l2;
end = l2;
l2 = l2.next;
}
}
if (l1 == null) {
end.next = l2;
} else if (l2 == null) {
end.next = l1;
}
}
}
``````

• @baisheng, when you want a queue, don't use ArrayList, you should use LinkedList. See http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist

• It's very helpful, and it works! Thank you so much!

• I got the same problem. Why quick sort won't do, that's stupid.

• My way is below:

1. divide list two parts L1 and L2
2. sort L1 and L2 recursively
3. merge L1 and L2
``````  ListNode* sortList(ListNode*  head){
ListNoide* l1,*l2;
l1 = sortList(l1);
l2 = sortList(l2);
return merge(l1,l2);
}
``````

• This post is deleted!

• This post is deleted!

• Bottom-up merge should be more efficient, but I still got TLE when I wrote in Java, any comments?

// merge sort by bottom-up

``````public ListNode sortList(ListNode head) {

}

while (queue.size() > 1) {
ListNode a = queue.get(0);
ListNode b = queue.get(0);
ListNode c = merge(a, b);
}

return queue.get(0);
}

ListNode merge(ListNode a, ListNode b) {
ListNode p = null;

if (a.val < b.val) {
p = a;
a = a.next;
}
else {
p = b;
b = b.next;
}

while (a != null && b != null) {
if (a.val < b.val) {
p.next = a;
p = p.next;
a = a.next;
}
else {
p.next = b;
p = p.next;
b = b.next;
}
}

if (a != null) {
p.next = a;
}
else if (b != null) {
p.next = b;
}

}
``````

• The time complexity of quick sort will degrade to O(n^2) in bad cases. I got TLE and then optimized my code a little further for cases where there are lots of duplicates. The code was accepted.

MAIN IDEA:

1. Node[`start_prev->next`] is chosen as sentinel, i.e. node[`mid`].

2. Nodes whose data are smaller than sentinel are append to `start_prev`.

3. Nodes whose data are equal to sentinal are append to `midTail`.

4. Other nodes are kept in place.

Sadly, my code doesn't meet the requirement "constant extra space" because it have to use a stack, no matter recursive or iterative.

Also, it will be still slow in the bad cases where the list are already sorted.

Maybe a function `isSorted` should be added to preclude these cases, but I doubt if it's worth it.
Looking forward for some suggestions.

BYW, I recommend LeetCode to add test cases where the list is already sorted and is holy long. After that I'll have to optimize my code again.

class Solution {
public:
void sort(ListNode start_prev, ListNode end){
if(start_prev->next == end) return;
ListNode *mid, *midTail;
mid = midTail = start_prev->next;
ListNode *prev = mid, *cur = prev->next;
while(cur != end){
if(cur->val < mid->val){
prev->next = cur->next;
cur->next = start_prev->next;
start_prev->next = cur;
}else if(cur->val == mid->val && prev != midTail){
prev->next = cur->next;
cur->next = midTail->next;
midTail->next = cur;
midTail = cur;
}else{
prev = cur;
}
cur = prev->next;
}
sort(start_prev, mid);
sort(midTail, end);
}

``````ListNode *sortList(ListNode *head) {