JAVA 5ms Quick Sort


  • 3
    W
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode left = new ListNode(0), leftHead = left;
        ListNode right = new ListNode(0), rightHead = right;
        ListNode mid = new ListNode(0), midHead = mid;
        int val = head.val;
        while(head != null){
            if(head.val < val){
                left.next = head;
                left = head;
            }  
            if(head.val > val){
                right.next = head;
                right = head;
            }
            if(head.val == val){
                mid.next = head;
                mid = head;
            }
            head = head.next;
        }
        left.next = null;
        right.next = null;
        mid.next = null;
        
        return concat(sortList(leftHead.next),midHead.next,sortList(rightHead.next));
        
    }
    public ListNode concat(ListNode left, ListNode mid, ListNode right){
        ListNode LeftTail = getTail(left);
        ListNode midTail = getTail(mid);
        midTail.next = right;
        if(LeftTail != null) {
            LeftTail.next = mid;
            return left;
        } else {
            return mid;
        }
    }
    public ListNode getTail(ListNode head){
        if(head == null) return head;
        while(head.next != null) head = head.next;
        return head;
    }

  • 1
    X

    Excuse me! Hello,wangzhengxu. your code is very good! but it has a defect. if the data in a asc order,it will n^2.


Log in to reply
 

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