QuickSort Solution got TLE


  • 0
    D

    Getting Time limit exceeded error. I tested it in eclipse, it works fine. Any suggestions?

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        //find last node as pivot
        ListNode pivot = findTail(head);
        
        head = partition(head);
    
        //find pivot node create two new list
        ListNode cur = head;
        ListNode pre = null;
        while(cur != pivot) {
            pre = cur;
            cur = cur.next;
        }
        //separate list to 1st half, pivot, 2nd half
        //pre could be null if pivot == head after partition
        if (pre != null) pre.next = null;
        ListNode head2 = pivot.next;
        pivot.next = null;
        
        head = sortList(head);
        head2 = sortList(head2);
        
        //connect all 3 half
        pre = findTail(head);
        pre.next = pivot;
        pivot.next = head2;
        
        return head;
    }
    
    private ListNode findTail(ListNode head) {
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
    
    private ListNode partition(ListNode head) {
        //find last node as pivot
        ListNode pivot = findTail(head);
        ListNode dummy = new ListNode(0);
        ListNode cur1 = dummy;
        ListNode cur2 = pivot;
        while(head != pivot) {
            if (head.val < pivot.val) {
                cur1.next = head;
                head = head.next;
                cur1 = cur1.next;
                cur1.next = null;
            } else {
                cur2.next = head;
                head = head.next;
                cur2 = cur2.next;
                cur2.next = null;
            }
        }
        cur1.next = pivot;
        return dummy.next;
    }

  • 0
    G

    Same happened to me!


  • 0

    Hi, I also tried my quicksort solution, i found doing 3-way partition can be more efficient than 2-way partition. Because there is one test case, containing just 1,2,3, lots of duplicates, this can lead to worst case of quick sort and lead to stack-overflow. Check my solution for reference: https://leetcode.com/discuss/89638/n-logn-quick-sort-in-place-solution-using-java-6ms-beats-90%


Log in to reply
 

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