Java QuickSort,4ms beat 98%


  • 0
    D
    public ListNode sortList(ListNode head) {
        ListNode tail = head;
        if(head == null) return null;
        while(tail.next != null) {
            tail = tail.next;
        }
        quickSort(head,tail);
        return head;
        
    }
    void quickSort(ListNode head,ListNode tail){
        if(head == tail) return;
        ListNode left = null;
        ListNode middle = null;
        ListNode right = head;
        while(right != tail){
            if(right.val < tail.val){
                middle = middle==null ? head:middle.next;
                left = left==null ? head:left.next;
                int tmp = right.val;
                right.val = middle.val;
                middle.val = left.val;
                left.val = tmp;
            }
            else if (right.val == tail.val){
                middle = middle==null ? head:middle.next;
                int tmp = right.val;
                right.val = middle.val;
                middle.val = tmp;
            }
            
            right = right.next;
        }
        if(middle == null) {
            int tmp = head.val;
            head.val = tail.val;
            tail.val = tmp;
            quickSort(head.next,tail);
        }
        else if(middle.next != tail){
            int tmp = middle.next.val;
            middle.next.val = tail.val;
            tail.val = tmp;
            quickSort(middle.next.next,tail);
        }
        if(left != null) quickSort(head,left);
       
    }

Log in to reply
 

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