Wei Wang Wei Wang - 1 month ago 16
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 {
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.