使用O(1)空间复杂度对O(n log n)中的链表进行排序

Question

这是LeetCode上的排序列表问题https://oj.leetcode.com/problems/sort-list/ 我制作了一个Java解决方案,但它导致超长测试用例超出时间限制.而且我在代码中找不到错误.谁能指出这个bug在哪里？非常感谢.

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 1

该错误可能是已排序列表上的快速排序O(n*n).一个实际的解决方案是随机选择枢轴.标准的在线油藏采样算法解决了这个问题.

然而,这仍然可能不够好.Quicksort将创建一个带O(log(n))调用的callstack ,因此占用O(log(n))空间.如果他们设置了足够好的测试,他们应该能够验证你已经过去了.

有关实际解决方案,请参阅http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf.

鉴于有多少人通过了这个问题,我怀疑他们没有准确地发现O(log(n))空间和O(1)空间之间的差异.