Wei Wang - 2 months ago 27

Java Question

This is Sort List problem on LeetCode https://oj.leetcode.com/problems/sort-list/

I made a Java solution but it caused Time Limit Exceeded on an extremely long test case. And I couldn't find the bug in my code. Could anyone point out where the bug is? Many thanks.

`class ListNode {`

int val;

ListNode next;

ListNode(int x) {

val = x;

next = null;

}

}

public class Solution {

public ListNode sortList(ListNode head) {

return this.sortPart(head, null);

}

private ListNode sortPart(ListNode start, ListNode end){

if(start == null)return null;

if(start == end)return start;

ListNode l=start, r=start, p=start.next;

while(p!= null && p!=end){

if(p.val < start.val){ // current node less than start node

r.next = p.next;

p.next = l;

l = p; // set current node as leftmost

p = start.next; // go to next node

}else{ // current node no less more start node

r = p; // set current node as rightmost and go to next node

p = p.next;

}

}

// recursively sort left part and right part

sortPart(l,start);

sortPart(start.next, r);

return l;

}

}

Answer

The bug is probably that a quicksort on an already sorted list is `O(n*n)`

. One practical solution is random selection of the pivot. The standard online reservoir sampling algorithm solves that.

However that still might not be good enough. Quicksort will create a callstack with `O(log(n))`

calls which therefore takes `O(log(n))`

space. If they set up good enough tests, they should be able to verify that you've gone over.

For a real solution, see http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf.

Given how many people have passed this problem, I suspect that they do not accurately catch the difference between `O(log(n))`

space and `O(1)`

space.