Non-recursive quicksort java TLE


  • 0
    D
    public class Solution {
        
    public ListNode sortList(ListNode head) {
    	// Non-recursive quicksort with constanct space complexcity
    	ListNode p = head;
    	ListNode q = head;
    	LinkedList<ListNode> list = new LinkedList<>();
    	int value = 0;
    	ListNode tail = null;
    	int pivotValue = 0;
    	ListNode prev = null;  //store the previous node of pivot
    	if(p != null){  //first iteration to get the tail
    		pivotValue = p.val;
    		ListNode pivotPos = p;
    		p.val = 0x7fffffff;  //the largest integer
    		while (q != null) {
    			if (q.val <= pivotValue) {
    				value = p.val;
    				if (value == 0x7fffffff){  //update the pivot position
    					pivotPos = q;
    				}
    				p.val = q.val;
    				q.val = value;
    				prev = p;
    				p = p.next;
    			}
    			tail = q;
    			q = q.next;
    		}
    		value = p.val;  //switch the value of p and pivot
    		p.val = pivotValue;
    		pivotPos.val = p.val;
    		
    	}
    	
    	list.addFirst(head);
    	list.addFirst(prev);
    	if (p != tail) {
    		list.addFirst(p.next);
    		list.addFirst(tail);
    	}
    	ListNode phead = head;
    	
    	while (list.size() != 0) {
    		tail = list.removeFirst();
    		phead = list.removeFirst();
    		if (tail == phead)
    			continue;
    		if (phead == null || tail == null)
    			continue;
    		p = phead;
    		q = phead;
    		value = p.val;
    		p.val = tail.val;
    		tail.val = value;
    		pivotValue = value;
    		prev = null;
    		while (q != tail) {
    			if (q.val <= pivotValue) {
    				value = p.val;
    				p.val = q.val;
    				q.val = value;
    				prev = p;
    				p = p.next;
    			}
    
    			q = q.next;
    		}
    		value = p.val;
    		p.val = tail.val;
    		tail.val = value;
    		list.addFirst(phead);
    		list.addFirst(prev);
    		if (p != tail) {
    			list.addFirst(p.next);
    			list.addFirst(tail);
    		}
    	}
    	return head;
    }    }

  • 0
    D

    My solution is not accepted and get a TLE. My idea is to use a stack to do non-recursive quicksort. I guess quicksort on some specific test cases is not O(nlgn). That's why TLE is got.


Log in to reply
 

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