Wei Wang - 1 year ago 148
Java Question

# Sort a linked list in O(n log n) with O(1) space complexity

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 {
}

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;
}
}
``````

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.
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.