Java quick sort. fast. beats 98% ; also includes merge sort code.


  • 8
    Z
    ListNode quickSort(final ListNode h){
        if(h == null || h.next == null)
            return h;
        
        /*split into three list*/
        ListNode fakesmall = new ListNode(0), small = fakesmall;
        ListNode fakelarge = new ListNode(0), large = fakelarge;
        ListNode fakeequal = new ListNode(0), equal = fakeequal;
        
        ListNode cur = h; // pivot is h.
        while(cur != null){
            if(cur.val < h.val){
                small.next = cur;
                small = small.next;
            }
            else if(cur.val == h.val){
                equal.next = cur;
                equal = equal.next;
            }
            else{
                large.next = cur;
                large = large.next;
            }
            
            cur = cur.next;
        }
        
        // put an end.
        small.next = equal.next = large.next = null;
        // merge them and return . merge reusing below one. merge for quicksort should be simplified. 
        return merge(merge(quickSort(fakesmall.next), quickSort(fakelarge.next)),fakeequal.next) ;
    }
    
    
    /*mrege sort*/
    ListNode mergeSort(ListNode h){
        if(h == null || h.next == null)
            return h;
        
        /*find cutting point*/    
        ListNode slow = h, cut = null, fast = h;
        while(fast != null && fast.next != null){
            cut = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        /*cut*/
        cut.next = null;
        
        return merge(mergeSort(h),mergeSort(slow));
    }
    
    ListNode merge(ListNode h, ListNode m){
        ListNode fake = new ListNode(0), cur = fake;
        
        while(h != null && m != null){
    
            if(h.val < m.val){
                cur.next = h;
                h = h.next;
            }
            else{
                cur.next = m;
                m = m.next;
            }
            cur = cur.next;
        }
        
        cur.next = (h == null ? m : h);
        
        return fake.next;
    }

  • 1

    Guess we're lucky with the test cases. For already-sorted inputs such pivot choice is O(n^2). I've tried randomized quicksort, but it obviously requires a full pass to determine the length so it wasn't so good (13 ms).


  • 0

    I just think quick sort will cost O(log N) space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.