Sharing my solution beat >99% submits


  • 0
    E

    Main idea is quick sort, and firstly I got time problem, and then I take pivot into consideration and then got the better solution.

    And here is my code.

    public ListNode sortList(ListNode head) {
            return partition(head, null);
        }
    
        public ListNode partition(ListNode head, ListNode end) {
        if (head == end)
            return end;
        if (head.next == end) {
            head.next = end;
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode t = dummy;
        while (t.next != end) {
            if (t.next.val < head.val) {
                ListNode temp = t.next;
                t.next = t.next.next;
                temp.next = dummy.next;
                dummy.next = temp;
            } else
                t = t.next;
        }
        
        ListNode pivotHead = head;
        while (head.next != null && head.val == head.next.val)
            head = head.next;
    
        t.next = end;
        dummy.next = partition(dummy.next, pivotHead);
        head.next = partition(head.next, end);
    
        return dummy.next;
    }

Log in to reply
 

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