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

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

On first glance this does not seem to work. Better comment what the algorithm wants to achieve with every step (=explain). Naming as `leftMost` might help too, making some current comments superfluous. — Joop Eggen, Oct 17 '14 at 16:32
The way you are manipulating pointers in the partitioning is very far from correct. See http://stackoverflow.com/questions/14805936/optimal-quicksort-for-single-linked-list . — Gene, Oct 17 '14 at 17:59
Thanks for the advice, it is quick sort, and I need to improve the implementation. — Wei Wang, Oct 22 '14 at 11:26

score 5 · Accepted Answer · answered Oct 17 '14 at 15:30

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.

Thanks a lot, it really points out where I didn't considered. — Wei Wang, Oct 22 '14 at 11:23

score 0 · Answer 2 · answered Oct 25 '16 at 13:02

0

I don't know why you went for quick sort...its worst case is O(n * n)....what you were looking for was Heap sort O(n+n*log(n)) eqiv. to O(nlog(n)) and with space complexity of O(1)

answered Oct 25 '16 at 13:02

RAHUL ROY

126
2
13

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

2 Answers2